二叉树中最大路径和[处理好任意一颗子树，就处理好了整个树]

前言

对于二叉树而言，利用好本身的递归体质，是解决问题的关键，处理好递归中任意一棵子树，就处理好了整个树。通过二叉树中最大路径和练习回溯+处理子树。

一、二叉树中最大路径和

二、回溯+处理子树

package everyday.hard;

// 二叉树中的最大路径和。
public class MaxPathSum {
    
    /* target：找到任意路径和最大的值。 从递归结构来看的话，左右子树想要有路径，那必然只能在左右子树选一个孩子，通过父节点连通。 而要选最大和的路径值，可用一个变量记录max即可。 */
    public int maxPathSum(TreeNode root) {
    
        // 在遍历过程中寻找最大值。
        order(root);
        // 返回寻找到的最大值。
        return max;
    }

    private int max = 1 << 31;

    private int order(TreeNode root) {
    
        // 访问到null节点，递归结束，返回贡献值0.
        if (null == root) return 0;
        // 回溯得到 左右值。
        int left = order(root.left);
        int right = order(root.right);
        // 四种可选路径，左根 | 右根 | 根 | 左根右
        // 返回的路径和只能在前三种中选最大值，而max化，需要在四种路径中取最大值。
        // 先找前三者谁大，谁大，返回谁；再和左根右比较，跟max比较，得到max.
        int rs = Math.max(left + root.val, Math.max(right + root.val, root.val));
        // 更新max
        max = Math.max(max, Math.max(rs, left + right + root.val));
        // 返回最大子路径和
        return rs;
    }

    // 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;
        }
    }

}

总结

1）处理好每一颗子树。
2）二叉树处理问题，要么从上到下，要么从下往上看问题。

参考文献

[1] LeetCode 二叉树中最大路径和