二叉树的深度和高度问题

L104 最大深度问题

给定一个二叉树,找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

image-20240206090837606

递归(后序)

先拿到左右子树的结果再计算Math.max(left,right) + 1,这与后序遍历本质上一样的,因此可以看做后序遍历的拓展问题。

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth =  maxDepth(root.left);
        int rightDepth =  maxDepth(root.right);
        return Math.max(leftDepth, rightDepth) + 1;
    }
}

层序遍历

只需要每一层遍历结束以后计数即可

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int depth = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode remove = queue.remove();
                if (remove.left != null) {
                    queue.add(remove.left);
                }
                if (remove.right != null) {
                    queue.add(remove.right);
                }
            }
            depth++;
        }

        return depth;
    }
}

L110 判断平衡树

首先分清楚高度与深度的区别

  • 二叉树节点的深度:指从根节点到该节点最⻓简单路径边的条数。
  • 二叉树节点的高度:指从该节点到叶子节点的最⻓简单路径边的条数

image

自下而上

和最大深度一样,首先找到最大深度,然后判断深度是否超过了2(也就是左右的差绝对值是否小于2),如果没有超过+1就行,超过的话直接返回-1;

 public boolean isBalanced(TreeNode root) {
        int res = recur(root);
        return res != -1;
    }

    public static int recur(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = recur(root.left);
        if (left == -1)
            return -1;
        int right = recur(root.right);
        if (right == -1)
            return -1;
        return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
    }

自上而下

 public static boolean isBalanced_2(TreeNode root) {
        if (root == null) return true;
        return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced_2(root.left) && isBalanced_2(root.right);
    }

    private static int depth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(depth(root.left), depth(root.right)) + 1;
    }

L111 最小深度

给定一个二叉树,找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

image-20240206110747964

递归

自底向上,最底下为1,往上则+1,MAX_VALUE+1 = 1

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

层序遍历

核心要点还是返回条件,当左右叶子节点都为空

  • 如果左子树为空,右子树不为空,说明最小深度是 1 + 右子树的深度。
  • 反之,右子树为空,左子树不为空,最小深度是 1 + 左子树的深度。
    最后如果左右子树都不为空,返回左右子树深度最小值 + 1
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int minDepth = 0;

        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        minDepth++; //这里不同第一题一点是,这里是先++,因为自上而下层序遍历需要每层+1
        while (!queue.isEmpty()) {
            int size = queue.size();
            minDepth++;
            for (int i = 0; i < size; i++) {
                TreeNode remove = queue.remove();
                if (remove.left == null && remove.right == null) {
                    return minDepth;
                }
                if (remove.left != null) {
                    queue.add(remove.left);
                }
                if (remove.right != null) {
                    queue.add(remove.right);
                }

            }

        }
        return minDepth;
    }
}

L559 N叉树的最大深度

给定一个 N 叉树,找到其最大深度。最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

image-20240206164119877

层序遍历

与先前的N叉树相同,核心要点在于使用一个集合将其子节点遍历,思想与二叉树相同

class Solution {
    public int maxDepth(Node root) {
        if (root == null) {
            return 0;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        int depth = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Node remove = queue.remove();
                List<Node> children = remove.children;
                for (Node nTreeNode : children) {
                    if (nTreeNode.children != null) {
                        queue.add(nTreeNode);
                    }
                }
            }
            depth++;

        }
        return depth;
    }
}

递归

递归的核心依然是将子节点的情况转换为List集合,但是需要先判断root.children 是否为null或者长度为空,否则会出现空指针异常

class Solution {
    public int maxDepth(Node root) {
       if (root == null) {
            return 0;
        }
        if (root.children==null||root.children.isEmpty()) {
            return 1;
        }
            List<Integer> heights = new LinkedList<Integer>();
         
            for (Node ch : root.children){
                heights.add(maxDepth(ch));
            }
            return Collections.max(heights)+1;
        }
    }