Java实现Leetcode题(二叉树)

2023-12-21 22:27:20

Leetcode144(前序遍历)

	//递归
    public static List<Integer> inorderTraversal(TreeNode root){
		List<Integer> list = new ArrayList<>();
		inorder(root,list);
		return list;
	}
	public static void inorder(TreeNode root,List<Integer> list) {
		if(root==null) {
			return;
		}
		list.add(root.val);
		inorder(root.left,list);
		inorder(root.right,list);
	}
    
    //迭代
    public static List<Integer> preorderTraversal(TreeNode root){
		List<Integer> list = new ArrayList<Integer>();
		Deque<TreeNode> de = new LinkedList<>();
		if(root==null) {
			return list;
		}
		de.addFirst(root);
		while(!de.isEmpty()) {
			TreeNode temp = de.peekFirst();
			de.pollFirst();
			list.add(temp.val);
			if(temp.right!=null) {
				de.addFirst(temp.right);
			}
			if(temp.left!=null) {
				de.addFirst(temp.left);
			}
		}
		return list;
	}

Leetcode145(后序遍历)?

//迭代法
public static List<Integer> postorderTraversal(TreeNode root){
		List<Integer> list = new ArrayList<>();
		Deque<TreeNode> de = new LinkedList<>();
		if(root==null) {
			return list;
		}
		de.addFirst(root);
		while(!de.isEmpty()) {
			TreeNode temp = de.peekFirst();
			de.pollFirst();
			list.add(temp.val);
			if(temp.left!=null) {
				de.addFirst(temp.left);
			}
			if(temp.right!=null) {
				de.addFirst(temp.right);
			}
		}
		Collections.reverse(list);
		return list;
	}

   //递归
    public static List<Integer> postorderTraversal(TreeNode root){
		List<Integer> list = new ArrayList<>();
		postorder(root,list);
		return list;
	}
	public static void postorder(TreeNode root,List<Integer> list) {
		postorder(root.left,list);
		postorder(root.right,list);
		list.add(root.val);
	}

Leetcode94(中序遍历)

//迭代
public static List<Integer> inorderTraversal(TreeNode root){
		List<Integer> list = new ArrayList<>();
		Deque<TreeNode> de = new LinkedList<>();
		if(root == null) {
			return list;
		}
		TreeNode cur = root;
		while(cur!=null||!de.isEmpty()) {
			if(cur!=null) {
				de.addFirst(cur);
				cur = cur.left;
			}else {
				cur = de.peekFirst();
				list.add(cur.val);
				de.pollFirst();
				cur = cur.right;
			}
		}
		return list;
	}
    //递归
    public static List<Integer> inorderTraveral(TreeNode root){
		List<Integer> list = new ArrayList<>();
		inorder(root,list);
		return list;	
	}
	
	public static void inorder(TreeNode root,List<Integer>list) {
		if(root==null) {
			return;
		}
		inorder(root.left,list);
		list.add(root.val);
		inorder(root.right,list);
	}
    


?

文章来源:https://blog.csdn.net/weixin_47059164/article/details/135139269
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。