二叉树的前，中，后序遍历，以及层序遍历。

2023-04-19 本文已影响0人盼旺

前 https://leetcode.cn/problems/binary-tree-preorder-traversal/
中 https://leetcode.cn/problems/binary-tree-inorder-traversal/
后 https://leetcode.cn/problems/binary-tree-postorder-traversal/
层 https://leetcode.cn/problems/binary-tree-level-order-traversal/

简单的递归法

前

class Solution {
    private List<Integer> rr = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        helper(root);
        return rr;
    }

    public void helper(TreeNode t){
            if(t==null){
                return;
            }
            rr.add(t.val);
            helper(t.left);
            helper(t.right);
    }
}

中

class Solution {
    private List<Integer> rr = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        helper(root);
        return rr;
    }
    public void helper(TreeNode t){
            if(t==null){
                return;
            }
            helper(t.left);
            rr.add(t.val);
            helper(t.right);
    }
}

后

class Solution {
     private List<Integer> rr = new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        helper(root);
        return rr;
    }
    public void helper(TreeNode t){
            if(t==null){
                return;
            }
            helper(t.left);
            helper(t.right);
            rr.add(t.val);
    }
}

利用栈的迭代

前

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

中

因为中序的根在中间，要先找到最左的节点，所以需要引入一个新的变量

栈S;
p= root;
while(p || S不空){
while(p){
p入S;
p = p的左子树;
}
p = S.top 出栈;
访问p;
p = p的右子树;
}

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

后

前序遍历的过程是根左右。
将其转化成根右左。也就是压栈的过程中优先压入左子树，在压入右子树。
然后将这个结果反向打印出来。

class Solution {
    private List<Integer> rr = new ArrayList<>();
    private List<Integer> rr2 = new ArrayList<>();
    private Stack<TreeNode> stack = new Stack<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root==null){
            return rr;
        }
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode t = stack.pop();
            if(t==null){
                continue;
            }
            rr.add(t.val);
            stack.push(t.left);
            stack.push(t.right);
        }
        for(int i=rr.size()-1;i>=0;i--){
            rr2.add(rr.get(i));
        }
        return rr2;
    }
}

颜色标记法

其核心思想如下：

使用颜色标记节点的状态，新节点为白色，已访问的节点为灰色。
如果遇到的节点为白色，则将其标记为灰色，然后将其右子节点、自身、左子节点依次入栈。
如果遇到的节点为灰色，则将节点的值输出。

前

class Solution {
    private List<Integer> rr = new ArrayList<>();
    private Stack<TreeNode> stack = new Stack<>();
    private Map<TreeNode,String> umap = new HashMap<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root==null){
            return rr;
        }
        stack.push(root);
        umap.put(root,"white");
        while(!stack.isEmpty()){
            TreeNode t = stack.pop();
            if(t==null){
                continue;
            }
            if(umap.get(t).equals("white")){
                umap.put(t,"grey");
                umap.put(t.right,"white");
                umap.put(t.left,"white");
                stack.push(t.right);
                stack.push(t.left);
                stack.push(t);
            }else{
                rr.add(t.val);
            }
        }
        return rr;
    }
}

中

class Solution {
    private List<Integer> rr = new ArrayList<>();
    private Stack<TreeNode> stack = new Stack<>();
    private Map<TreeNode,String> umap = new HashMap<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root==null){
            return rr;
        }
        stack.push(root);
        umap.put(root,"white");
        while(!stack.isEmpty()){
            TreeNode t = stack.pop();
            if(t==null){
                continue;
            }
            if(umap.get(t).equals("white")){
                umap.put(t,"grey");
                umap.put(t.right,"white");
                umap.put(t.left,"white");
                stack.push(t.right);
                stack.push(t);
                stack.push(t.left);
            }else{
                rr.add(t.val);
            }
        }
        return rr;
    }
}

后

class Solution {
    private List<Integer> rr = new ArrayList<>();
    private Stack<TreeNode> stack = new Stack<>();
    private Map<TreeNode,String> umap = new HashMap<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root==null){
            return rr;
        }
        stack.push(root);
        umap.put(root,"white");
        while(!stack.isEmpty()){
            TreeNode t = stack.pop();
            if(t==null){
                continue;
            }
            if(umap.get(t).equals("white")){
                umap.put(t,"grey");
                umap.put(t.right,"white");
                umap.put(t.left,"white");
                stack.push(t);
                stack.push(t.right);
                stack.push(t.left);
            }else{
                rr.add(t.val);
            }
        }
        return rr;
    }
}

层序遍历-从第一层到最后一层

BFS加队列Queue(LinkedList)就可以,核心点就是for循环那一层的所有节点。

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> rr = new ArrayList<>();
        if(root==null){
            return rr;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int nowSize = queue.size();
            List<Integer> rr2 = new ArrayList<>();
            for(int i = 0 ;i<nowSize;i++){
                TreeNode t = queue.poll();
                rr2.add(t.val);
                if(t.left!=null){
                    queue.add(t.left);
                }
                if(t.right!=null){
                    queue.add(t.right);
                }  
            }
            rr.add(new ArrayList<>(rr2));
        }
        return rr;
    }
}

层序遍历-从最后一层到第一层

把上面的结果反着输出就好了

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> rr = new ArrayList<>();
        List<List<Integer>> rr3 = new ArrayList<>();

        if(root==null){
            return rr;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int nowSize = queue.size();
            List<Integer> rr2 = new ArrayList<>();
            for(int i = 0 ;i<nowSize;i++){
                TreeNode t = queue.poll();
                rr2.add(t.val);
                if(t.left!=null){
                    queue.add(t.left);
                }
                if(t.right!=null){
                    queue.add(t.right);
                }  
            }
            rr.add(new ArrayList<>(rr2));
        }
        for(int i=rr.size()-1;i>=0;i--){
            rr3.add(rr.get(i));
        }
        return rr3;
    }
}

二叉树的最小深度

关键是搞清楚递归结束条件

叶子节点的定义是左孩子和右孩子都为 null 时叫做叶子节点
当 root 节点为空时，返回 0
当 root 节点左右孩子都为空时，返回 1 这是叶子节点
当 root 节点左右孩子有一个为空时，返回不为空的孩子节点的深度因为没有到叶子节点还得继续往下走。
当 root 节点左右孩子都不为空时，返回左右孩子较小深度的节点值

class Solution {
    public int minDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        if(root.left==null||root.right==null){
            return Math.max(minDepth(root.left),minDepth(root.right))+1;
        }
        if(root.left==null&&root.right==null){
            return 1;
        }
        return  Math.min(minDepth(root.left),minDepth(root.right))+1;
    }
}

判断它是否是高度平衡的二叉树。

一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 。
思路是对二叉树做先序遍历，从底至顶返回子树最大高度，若判定某子树不是平衡树则 “剪枝” ，直接向上返回。

算法流程：
recur(root):

递归返回值：
当节点 root 左 / 右子树的高度差 < 2 ;则返回以节点 root 为根节点的子树的最大高度，即节点 root 的左右子树中最大高度加 1（ max(left, right) + 1 ）；
当节点 root 左 / 右子树的高度差 ≥2 ：则返回 −1 ，代表此子树不是平衡树。
递归终止条件：
当越过叶子节点时，返回高度 0；
当左（右）子树高度 height== -1 时，代表此子树的左（右）子树不是平衡树，因此直接返回 −1 ；
isBalanced(root) ：
返回值：若 recur(root) != -1 ，则说明此树平衡，返回 true ；否则返回 false 。

先看这个代码

class Solution {
    public boolean isBalanced(TreeNode root) {
        return dfs(root)[0] == 1;
    }

    private int[] dfs(TreeNode root){
        if(root == null)return new int[]{1, 0};
        int[] result = new int[2];// result[0]表示当前节点受否符合二叉树，1为true，0为false；result[1]表示当前节点的高度

        int[] left = dfs(root.left);// 递归计算左子树
        int[] right = dfs(root.right);// 递归计算右子树

        result[1] = Math.max(left[1], right[1]) + 1;// 当前节点高度

        int minus = Math.abs(left[1] - right[1]);// 左右子树的高度差的绝对值

        result[0] = left[0] & right[0] & (minus < 2 ? 1 : 0);
        return result;
    }
}

优化后

class Solution {
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }
//返回节点node的最大深度。
    public int getHeight(TreeNode node){
        if (node == null) {
            return 0;
        }
        int leftH = getHeight(node.left);
        if(leftH == -1) return -1;
        int rightH = getHeight(node.right);
        if(rightH == -1) return -1;
        return Math.abs(leftH-rightH)>=2?-1:Math.max(leftH,rightH)+1;
    }
}