LeetCode --- 二叉树操作

543. 二叉树的直径

乍看是 根节点的 左子树最大高度 + 右子树最大高度 + 1

但其实不能这样，因为路径可能并不经过根节点，如图二

因此要用一个 max 来保存最后的最大路径和

在求二叉树高度的递归中，在每个根节点（在递归函数中），比较 max 与 以这个当前根节点的  左子树最大高度 + 右子树最大高度 + 1 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    private static int maxDiameter = 0;

    public Solution() {
        maxDiameter = 0;
    }

    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        // 在递归求树高的过程中求出来的 maxDiameter
        return maxDiameter;
    }

    private int dfs(TreeNode nowRoot) {
        if (nowRoot == null) {
            return 0;
        }
        int leftHeight = dfs(nowRoot.left);
        int rightHeight = dfs(nowRoot.right);

        // 路径长度最大值为左子树 + 右子树高度,与之前的最大值比较
        maxDiameter = Math.max(leftHeight + rightHeight, maxDiameter);

        // 因为要通过递归求树高度，所以最后仍要返回高度：左右子树中较高的那个（而不是路径和）
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

124. 二叉树中的最大路径和

最大路径怎么求？

最后的最大路径，任一节点 都有可能作为这个最大路径的根节点

所以有一个全局的最大路径 maxPathSum， 每次递归的时候（在每个根节点）都要与之比较

又如果当前节点作为 最后最大路径的根节点，那么 只当前根节点/当前根节点+左子树/当前根节点+右子树/当前根节点+左子树+右子树 这四种情况都行

所以，要取这四种情况中最大的来与 maxPathSum 比较，这四种一定会包含当前根节点，所以四种中最大的求法就是：初始值为当前根节点的值，左子树>0 就加左子树，右子树>0 就加右子树

递归的返回值应该是什么？

之前比较路径的时候，由于当前节点可能作为最后最长路径的根，所以要把四种情况都算上

但是返回的时候，当前节点的情况是作为之后的一些结果的子集，这时候当前节点一定不能为最长路径的根节点

所以要么选择左分支 root.val + leftSum，要么选择右分支 root.val + rightSum

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    private static int maxPathSum = Integer.MIN_VALUE;

    public Solution() {
        maxPathSum = Integer.MIN_VALUE;
    }

    public int maxPathSum(TreeNode root) {
        dfs(root);
        return maxPathSum;
    }

    private int dfs(TreeNode root) {
        int thisRootSum = 0;
        if (root == null) {
            return thisRootSum;
        }

        int leftSum = dfs(root.left);
        int rightSum = dfs(root.right);
        
        // 最长路径可能以任一结点为根。只当前根节点/根节点+左子树/根节点+右子树/根节点+左子树+右子树 这四种情况都行，选出这四种情况下最大的
        int thisRootMax = root.val;
        if (leftSum > 0) {
            thisRootMax += leftSum;
        }
        if (rightSum > 0) {
            thisRootMax += rightSum;
        }
        // 最长路径可能以任一结点为根，所以每个节点的最大与之前的最大比较一下
        maxPathSum = Math.max(maxPathSum, thisRootMax);
        
        // 之前比较路径的时候，由于当前节点可能作为最后最长路径的根，所以要把四种情况都算上
        // 但是返回的时候，是作为之后的一些结果的子集，这时候当前节点一定不能为最长路径的根节点
        // 所以要么选择左分支 root.val + leftSum，要么选择右分支 root.val + rightSum
        int chooseLeftOrRightMax = Math.max(root.val + leftSum, root.val + rightSum);
        // 收益小于0，直接舍弃
        if (chooseLeftOrRightMax < 0) {
            chooseLeftOrRightMax = 0;
        }
        return chooseLeftOrRightMax;
    }
}