知识点

LeetCode算法题

1. LeetCode算法题

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

      解题思路：

      二叉树问题必定使用递归，递归的核心就是将原问题拆分成子问题。

      首先，对于过某个节点（非root节点）的最大路径有3种情况备选：过左节点最大路径+自己+父节点、过右节点最大路径+自己+父节点、过左节点最大路径+自己+过右节点最大路径。当前节点的最大路径和从这三种情况选择一个即可。

      过左节点最大路径+自己、过右节点最大路径+自己可以通过递归计算，递归函数如下：

       public int dfs(TreeNode root) {
       if (root == null) {
           return 0;
       }
       //计算左边分支最大值，左边分支如果为负数还不如不选择
       int leftMax = Math.max(0, dfs(root.left));
       //计算右边分支最大值，右边分支如果为负数还不如不选择
       int rightMax = Math.max(0, dfs(root.right));
      
       // 返回经过root的单边最大分支给当前root的父节点计算使用
       return root.val + Math.max(leftMax, rightMax);
      }

      因为递归函数体中，左右节点最大路径已经计算出来，因此可以定义一个全局变量max，存储最大的路径和，遍历全部节点计算并更新max，最终返回max。最终算法如下：

       int max = Integer.MIN_VALUE;
      public int maxPathSum(TreeNode root) {
       if (root == null) {
           return 0;
       }
       dfs(root);
       return max;
      }
      
      /**
      * 返回经过root的单边分支最大和， 即Math.max(root, root+left, root+right)
      * @param root
      * @return
      */
      public int dfs(TreeNode root) {
       if (root == null) {
           return 0;
       }
       //计算左边分支最大值，左边分支如果为负数还不如不选择
       int leftMax = Math.max(0, dfs(root.left));
       //计算右边分支最大值，右边分支如果为负数还不如不选择
       int rightMax = Math.max(0, dfs(root.right));
       //left->root->right 作为路径与已经计算过历史最大值做比较
       max = Math.max(max, root.val + leftMax + rightMax);
       // 返回经过root的单边最大分支给当前root的父节点计算使用
       return root.val + Math.max(leftMax, rightMax);
      }