leetcode104.二叉树的最大深度,559.N叉树的最大深

二叉树的最大深度

题目链接

思路：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)

执行结果: