二叉樹的最大深度
思路：recursion
本題遞歸的思路比迭代要容易很多，遞歸的終止條件為：
當(dāng)前節(jié)點(diǎn)為空，返回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));
}
}
時(shí)間復(fù)雜度：每個(gè)節(jié)點(diǎn)都訪問(wèn)了一次，所以時(shí)間復(fù)雜度為O(N)
額外空間復(fù)雜度：遞歸的最大深度為當(dāng)這棵樹退化為線性鏈表，為O(N),當(dāng)這棵樹為平衡二叉樹的時(shí)候，遞歸深度為O(logN)
執(zhí)行結(jié)果:
N叉樹的最大深度
思路：recursion
同104題一樣，N叉樹的最大深度也應(yīng)該使用遞歸的思想
遞歸的終止條件為：當(dāng)前遍歷的節(jié)點(diǎn)為空，返回0
每層遞歸需要做的事是求出當(dāng)前子節(jié)點(diǎn)的最大深度，對(duì)所有的子節(jié)點(diǎn)的深度求出最大值，然后返回這個(gè)最大值 + 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;
}
}
時(shí)間復(fù)雜度：O(N)
額外空間復(fù)雜度：O(N),最好的情況下，也就是當(dāng)樹為平衡二叉樹的時(shí)候，額外空間復(fù)雜度為O(logN)
執(zhí)行結(jié)果:
