题目一：二叉树的深度
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
练习地址
https://www.nowcoder.com/practice/435fb86331474282a3499955f0a41e8b
https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/
参考答案
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public int TreeDepth(TreeNode root) {
if (root == null) {
return 0;
}
return Math.max(TreeDepth(root.left), TreeDepth(root.right)) + 1;
}
}
复杂度分析
- 时间复杂度：O(n)。
- 空间复杂度：O(n)。
题目二：平衡二叉树
输入一棵二叉树，判断该二叉树是否是平衡二叉树。如果某二叉树中任意节点的左、右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
练习地址
https://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222
https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/
需要重复遍历节点多次的解法，简单但不足以打动面试官
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
if (root == null) {
return true;
}
if (Math.abs(TreeDepth(root.left) - TreeDepth(root.right)) > 1) {
return false;
}
return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
}
public int TreeDepth(TreeNode root) {
if (root == null) {
return 0;
}
return Math.max(TreeDepth(root.left), TreeDepth(root.right)) + 1;
}
}
复杂度分析
- 时间复杂度：O(n^2)。
- 空间复杂度：O(n)。参考：
平均时间复杂度：O(log1+log2+...+logn)=O(log(n!))=O(nlogn)
每个节点只遍历一次的解法，正是面试官喜欢的
public class Solution {
private int mDepth;
public boolean IsBalanced_Solution(TreeNode root) {
if (root == null) {
mDepth = 0;
return true;
}
if (!IsBalanced_Solution(root.left)) {
return false;
}
int left = mDepth;
if (!IsBalanced_Solution(root.right)) {
return false;
}
int right = mDepth;
int diff = left - right;
if (diff <= 1 && diff >= -1) {
mDepth = 1 + (left > right ? left : right);
return true;
} else {
return false;
}
}
}
复杂度分析
- 时间复杂度：O(n)。
- 空间复杂度：O(n)。
