https://leetcode.com/problems/maximum-depth-of-n-ary-tree/
简化版：https://leetcode.com/problems/maximum-depth-of-binary-tree/

日期	是否一次通过	comment
2019-01-16 23:13	非递归一次通过；递归方法输出了所有元素的个数，而非最大深度	对递归遍历的方式理解不透

image.png

（来源： https://leetcode.com/problems/maximum-depth-of-n-ary-tree/）

---

此后约定：存进Queue 或者Stack的对象一定不能是null。

---

1. 非递归方法：实际上是BFS按层级遍历；
2. 递归方法：
   2.1 套用分层遍历：保留每一层的最大深度，而不是每个数量；
   2.2 递归思想：不停的分治，最大深度 = MAX(左子树最大深度， 右字数最大深度)

1. 非递归

class Solution {
    public int maxDepth(Node root) {
        if(root == null) {
            return 0;
        }
        
        Queue<Node> nodeQ = new LinkedList<>();
        nodeQ.offer(root);
        int depth = 0;
        
        while(!nodeQ.isEmpty()) {
            int width = nodeQ.size();
            for(int i=0; i<width; i++) {
                Node node = nodeQ.poll();
                for(Node nc : node.children) {
                    if(nc == null) {  // **********************
                          continue;
                    }
                    nodeQ.offer(nc);
                }
            }
            depth += 1;
        }
        
        return depth;
    }
}

2.1 递归

class Solution {
    public int maxDepth(Node root) {
        if(root == null) {
            return 0;
        }
        
        int[] depth = new int[]{0};
        helper(root, depth, 0);
        
        return depth[0] + 1;   // ********* 
    }
    
    private void helper(Node root, int[] depth, int level) {
     
        if(root == null) {
            return;
        }
        
        depth[0] = Math.max(depth[0], level);    // *****如果直接depth[0] ++，则返回树的所有节点数
        for(Node node : root.children) {
            helper(node, depth, level+1);
        }
        
    }
}

2.2 递归

class Solution {
    public int maxDepth(Node root) {
        if(root == null) {
            return 0;
        }
        
        int tempMax = 0;
        for(Node node : root.children) {
            tempMax = Math.max(tempMax, maxDepth(node));
        }
        
        return tempMax + 1;
    }
}

---

简单来说

2.1 套用了分层模板，但要注意全局要保存的是树的最大深度，而不是每次递归调用后的累加值，否则获取到的是节点的个数；

2.2 用的是分治的思想，最大深度=MAX(左子树最大深度, 右子树最大深度)；其中所谓的深度+1的操作依靠最后一行return时+1，这个+1或许可以理解为加上自身（当前节点）：

于是，

1. 如果是获取所有树的所有节点数，只要把tempMax = Math.max(tempMax, maxDepth(node));改为tempMax += maxDepth(node);即可；
2. 如果要计算树所有节点的value之和，则把tempMax = Math.max(tempMax, maxDepth(node));改为tempMax += maxDepth(node);，且return return tempMax + 1;改为return return tempMax + root.val;。

又，理解递归，其实把函数名maxDepth，换成hhd，这样看或许更能够看到整个递归的过程（实质），而不是在脑海中根据函数名陷入为主的YY。