二叉树的最大深度
思路：recursion
本题递归的思路比迭代要容易很多，递归的终止条件为：
当前节点为空，返回0
否则返回左右树最大深度 + 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) {
// 1. recursion
if(root == null){
return 0;
}
return 1 + Math.max(maxDepth(root.left),maxDepth(root.right));
}
}
时间复杂度：每个节点都访问了一次，所以时间复杂度为O(N)
额外空间复杂度：递归的最大深度为当这棵树退化为线性链表，为O(N),当这棵树为平衡二叉树的时候，递归深度为O(logN)
执行结果:
N叉树的最大深度
思路：recursion
同104题一样，N叉树的最大深度也应该使用递归的思想
递归的终止条件为：当前遍历的节点为空，返回0
每层递归需要做的事是求出当前子节点的最大深度，对所有的子节点的深度求出最大值，然后返回这个最大值 + 1即可
代码如下：
/*
// Definition for a Node.
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;
}
};
*/
class Solution {
public int maxDepth(Node root) {
if(root == null){
return 0;
}
int childrenMaxHeight = 0;
for(Node node : root.children){
childrenMaxHeight = Math.max(maxDepth(node),childrenMaxHeight);
}
return childrenMaxHeight + 1;
}
}
时间复杂度：O(N)
额外空间复杂度：O(N),最好的情况下，也就是当树为平衡二叉树的时候，额外空间复杂度为O(logN)
执行结果:
