543. Diameter of Binary Tree （Easy）高频 和124搭配

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree

          1
         / \
        2   3
       / \     
      4   5

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note:The length of path between two nodes is represented by the number of edges between them.

Solution 1: Recursive O(n); O(h) 基于104的代码

Foreverynode, length of longest path whichpass it= MaxDepth of its left subtree + MaxDepth of its right subtree.
After getting the length, compare it with current node's left and right subtree's diameter.

    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //如果最长路径算的是节点数，cur要多加1。
        int cur = maxDepth(root.left) + maxDepth(root.right);
        int left = diameterOfBinaryTree(root.left);
        int right = diameterOfBinaryTree(root.right);

        return Math.max(cur, Math.max(left, right));
    }

    public int maxDepth(TreeNode root) { //和第104题代码一模一样，求以当前节点为根结点的最大深度
        if (root == null) {
            return 0;
        }

        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }

Solution 2: Recursive O(n); O(h) 基于124的代码

Foreverynode, length of longest path whichpass it= MaxDepth of its left subtree + MaxDepth of its right subtree.

    int max = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        maxDepth(root);
        return max;
    }

    private int maxDepth(TreeNode root) {
        if (root == null) return 0;

        int left = maxDepth(root.left);
        int right = maxDepth(root.right);

        max = Math.max(max, left + right); //如果最长路径算的是节点数，left+right+1。

        return Math.max(left, right) + 1;
    }

124代码如下

    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        maxPathSubtree(root);
        return max;
    }

    private int maxPathSubtree(TreeNode node) {
        if (node == null) {
            return 0;
        }
        //since node's value can be negative, we need to compare the return value with 0.
        int left = Math.max(0, maxPathSubtree(node.left)); 
        int right = Math.max(0, maxPathSubtree(node.right));
        max = Math.max(max, left + right + node.val);
        return Math.max(left, right) + node.val;
    }

Follow Up:

1.找二叉树最长路径，针对第二题，followup问了好多递归相关