给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例： 给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。 ——
题意
- 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
- 根据树的定义可知,此题需要递归或者借助栈求解。
树的定义
树是n个结点的有限集合。在任意一颗非空树中：（1）有且仅有一个特定的称为根（root）的结点；（2）当n>1时,其余结点可分为m(m>0)个互补相交的有限集合T1,T2,T3….Tm,其中每个集合本身又是一颗树,并且称为根的子树。
思路
递归的思想是把大的问题，分解成小的同等的问题，最终会有一个终止条件，我们只需先序遍历整棵树，然后，每进入一层递归，树的深度就加1，然后比较当前结点（子树的根）的左右子树深度，选深度较大的与当前树的深度累加，退出当前递归调用。 ## 先序遍历
先根->左子树->右子树
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
int max=0;//存储子树的深度
int leftMax=0;
int rightMax=0;
if (root != null) {//如果当前子树不为空,非空树
max++;//深度加1
leftMax = maxDepth(root.left);//左子树深度
rightMax = maxDepth(root.right);//右子树深度
max += leftMax >= rightMax ? leftMax : rightMax;//当前子树的深度
}
return max;//返回当前子树的深度
}
}
总结
- 主要是需要了解树的基本定义,和递归调用的原理。
- 此题还有非递归版本，借助栈实现。其实方法递归调用也是同样的原理，jvm内存模型有个线程栈，有兴趣的同学可以自行