【1错-1】Diameter of Binary Tree

https://leetcode.com/problems/diameter-of-binary-tree/

日期	是否一次通过	comment
2019-01-18 23:13	否	maxDepth的扩展。理解好“分治”，左子树、右子树
2019-01-19 20:34	Y	对maxDepth理解加深

image.png

（来源： https://leetcode.com/problems/diameter-of-binary-tree/）

1. 非递归方法：TODO；
2. 递归方法：
   2.1 递归思想：不停的分治，result=左子树最大深度+ 右字数最大深度，于是题目转化成为“求最大树的最大深度，同时记录最大的左子树和右子树最大深度之和”

1. 非递归

2.1 递归

class Solution {
    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null) {
            return 0;
        }
        
        int[] rst = new int[]{0};
        helper(root, rst);
        return rst[0];
    }
    
    private int helper(TreeNode root, int[] rst) {
        
        if(root == null) {
            return 0;
        }
        
        int leftDpt = helper(root.left, rst);
        int rightDpt = helper(root.right, rst);
        rst[0] = Math.max(rst[0], leftDpt+rightDpt);
        
        return Math.max(leftDpt, rightDpt) + 1;
    }
}