每日分享 – 算法(八) 二叉树遍历

二叉树遍历

  • 前序遍历 根 + 左 + 右
  • 中序遍历 左 + 中 + 右
  • 后序遍历 左 + 右 + 中
  • 层序遍历 来自leetcode102，方法主要用广搜或队列，就不在这里写了。
  • 二叉树遍历一般就是递归和非递归

1，递归

简单，但是一般面试不考。都是用迭代的。

前序遍历

来自LeetCode144

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        traversal(root,res);
        return res;
    }

    public void traversal(TreeNode cur,List<Integer> res){
        if(cur == null)
            return;
        res.add(cur.val);
        traversal(cur.left,res);
        traversal(cur.right,res);
    }
}

中序遍历

来自LeetCode94

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        traversal(root,res);
        return res;
    }
    public void traversal(TreeNode cur,List<Integer> res){
        if(cur == null)
            return;
  
        traversal(cur.left,res);
        res.add(cur.val);
        traversal(cur.right,res);
    }
}

后序遍历

来自LeetCode145

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        traversal(root,res);
        return res;
    }

    public void traversal(TreeNode cur,List<Integer> res){
        if(cur == null)
            return;
  
        traversal(cur.left,res);
        traversal(cur.right,res);
        res.add(cur.val);
    }
}

2，非递归/迭代

前序遍历

运用栈存入，出栈时存入该节点的左右节点。

注意的是栈的特性，所以应该先传入right再传入左。

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode cur = root;
        if( cur == null)
            return list;
        stack.push(cur);
        while(!stack.isEmpty()){
            cur = stack.pop();
            list.add(cur.val);
            if(cur.right!=null) stack.push(cur.right);
            if(cur.left!=null) stack.push(cur.left);
        }
        return list;
    }
}

中序遍历

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while(cur!=null||!stack.isEmpty()){
            if(cur!=null){
                stack.push(cur);
                cur = cur.left;
            }
            else{
                cur = stack.pop();
                list.add(cur.val);
                cur = cur.right;
            }
        }
        return list;
    }
}

简称为左链入栈，就是左链先全部入栈，最后考虑右节点的情况。

记牢！！！！！！！！！！！！！！！！！

后序遍历

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        if(root == null)
            return list;
        TreeNode cur = root;
        TreeNode pre = null;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.peek();
            if(cur.right==null||cur.right==pre){
                pre = stack.pop();
                list.add(pre.val);
                cur = null;
            }else{
                cur = cur.right;
            }  
        }
        return list;
    }
}

其实和中序遍历差不多。更难写。

特殊方法：Morris 遍历

将空间复杂度从O(n)变成O(1)。

有空再实现吧

正文完
2022-11-19