Question
求二叉树的最大深度
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
二叉树的定义
// Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
Solutions
public class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int left = maxDepth(root.left);
int right = maxDepth(root.right);
return Math.max(left, right) + 1;
}
}
一开始忘记max函数怎么用，就写成了这样
if (left > right) {
return left + 1;
} else {
return right + 1;
}
One Line Show
return (root == null) ? 0 : Math.max(maxDepth(root.left) + 1, maxDepth(root.right) + 1);
Points
-
二叉树的数组表现
[1,null,2,3]这样的数组，顺序为从上往下每行中的从左到右的节点。
null表示空节点。[]表示空树。
array[i]的左子树为array[i*2]，右子树为array[i*2+1]。BinaryTree.png 节点为null的处理
if (root == null) {
return 0;
}
-
递归的效率
当一个函数用它自己来定义时，就称为递归（recursive）的；纱布如我一开始是这样写的
if (maxDepth(root.left) >= maxDepth(root.right)) {
return maxDepth(root.left) + 1;
} else {
return maxDepth(root.right) + 1;
}
多么直观，然后就感人的Time Limit Exceeded了。
这里大概是因为每次调用一次maxDepth都进行了一次递归，所以应该把maxDepth的结果保存成值再进行比较和返回。
这样写就没问题了
int left = maxDepth(root.left);
int right = maxDepth(root.right);
if (left > right) {
return left + 1;
} else {
return right + 1;
}
然后再精简点
return Math.max(maxDepth(root.right), maxDepth(root.left)) + 1;
TO DO
- 二叉树相关概念
- Math.max 源码分析
