算法通关村第八关|白银|二叉树的深度和高度问题【持续更新】

1.最大深度问题（后序遍历）

只需要一直递归，维护一个最大值。每一层只要有一个子节点，这个最大值就可以增加。

public int maxDepth(TreeNode root) {
	if (root == null) {
        return 0;
	}
	int leftHeight = maxDepth(root.left);
	int rightHeight = maxDepth(root.right);
	// 这里要+1，不要漏掉root节点
	return Math.max(leftHeight, rightHeight) + 1;
}
1
2
3
4
5
6
7
8
9

2.最大深度问题（层次遍历）

遍历出多少层，那么最大深度就是多少。

public int maxDepth(TreeNode root) {
	if (root == null) {
        return 0;
	}
	Queue<TreeNode> queue = new LinkedList<TreeNode>();
	queue.offer(root);
	int ans = 0;
	while (!queue.isEmpty()) {
        int size = queue.size();
        while (size > 0) {
            TreeNode node = queue.poll();
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
            size--;
        }
        ans++;
    }
	return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

3.判断高度平衡二叉树

本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 。
二叉树的高度：从该节点到叶子节点的节点数。

public Solution {
    public boolean isBalanced(TreeNode root) {
        return height(root) >= 0;
    }

    public int height(TreeNode root) {
        if (root == null) {
            return 0;
    	}
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        } else {
            return Math.max(leftHeight, rightHeight) + 1;
        }
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

4.最小深度（递归）

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

是要有叶子节点才可以算最小深度的，所以当一个节点的一个子树为空，一个不为空的时候，要从不为空的子树继续算深度，不能直接返回结果。

public int minDepth(TreeNode root) {
	if (root == null) {
        return 0;
	}
	if (root.left == null && root.right == null) {
        return 1;
    }

    // 定义一个min_depth，比较left和right的大小（如果不为空的话）
	int min_depth = Integer.MAX_VALUE;
	if (root.left != null) {
        min_depth = Math.min(minDepth(root.left), min_depth);
    }
	if (root.right != null) {
        min_depth = Math.min(minDepth(root.right), min_depth);
    }
	return min_depth + 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

5.最小深度（层次遍历）

找到第一个叶子节点即可。

public int minDepth(TreeNode root) {
	if (root == null) {
        return 0;
	}
	int minDepth = 0;
	LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
	queue.add(root);
	while (queue.size() > 0) {
        int size = queue.size();
        minDepth++;
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            // 先判断是不是叶子节点，是就直接返回值
            if (node.left == null && node.right == null) {
                return minDepth;
            }
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
    }
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

6.N叉树的最大深度

N叉树的定义：

class Node {
    public int val;
    public List<Node> children;

    public Node() {}
    public Node(int _val) {
        val = _val;
    }
    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

N叉树的最大深度（递归）

用一个增强 for 循环遍历每个子树即可。

class Solution {
    public int maxDepth(Node root) {
        if (root == null) {
            return 0;
        } else if (root.children.isEmpty()) {
            return 1;
        } else {
            int max = 0;
            for (Node item : root.children) {
                int childrendepth = maxDepth(item);
                max = Math.max(max, childrendepth);
            }
            return max + 1;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

N叉树的最大深度（层次遍历）

【持续更新】。

如果对您有帮助，请点赞关注支持我，谢谢！❤
如有错误或者不足之处，敬请指正！❤
个人主页：星不易 ❤
算法通关村专栏：不易|算法通关村 ❤