124. Binary Tree Maximum Path Sum; 543. Diameter of Binary Tree; 687. Longest Univalue Path;

124. Binary Tree Maximum Path Sum

问题：

求出给定二叉树中，最大路径和（节点权值相加）。（至少包含树中一个节点）

Example 1:
Input: [1,2,3]
       1
      / 
     2   3
Output: 6

Example 2:
Input: [-10,9,20,null,null,15,7]
   -10
   / 
  9  20
    /  
   15   7
Output: 42

　　

解法：Binary Tree（二叉树）

由于本问题要利用递归求解，

那么递归中，必定含有一个联系上下文的变量root，

我们定义递归函数为，包含root节点为止，的最大path。

那么该递归函数help有以下特性：

1. 包含当前root节点

2. 只包含左右子树之一 or 两者都不包含。（最大path：若两子树都包含，那么在上层调用中，解只有 root+两个子树，无法向上传递，做出选择）

而我们利用help递归，要得到的真正的解为：

  • 假设使用help求得了，左子树，右子树的最大路径 
    • l = help(root->left)
    • r = help(root->right)
  • 对树中每个节点：
  • MAX{
    • 只选择root
    • 选择root+左子树
    • 选择root+右子树
    • 选择root+左子树+右子树
  • }

即：

res = max(res, 

root + max(l, 0) + max(r, 0)

)

对于递归函数help：

  • DEF：
    • 包含root的，最大单侧子树路径。
  • STAT：
    • root
  • OPT：得到递归解 l 和 r
    • return max(root+l, root+r)
  • BASE：
    • if root==null, then return 0

代码参考：

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 8  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 9  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10  * };
11  */
12 class Solution {
13 public:
14     // RECURSION:
15     //DEF: fun help(root):
16     //    get the max path of one side, through current root node:
17     //     [As a child res] of the whole question.
18     //    (we need transfer this res to the upper question)
19     //    1. contains the current root node.
20     //    2. only contains one side child of this root node, or neither to choose(only root).
21     //   = root->val + MAX {
22     //      left child,
23     //      right child,
24     //      0
25     //     }
26     //STAT: root
27     //OPT: 
28     //  return root+ l or r(max)
29     //BASE:
30     // if root==null then: return 0;
31     //
32     // REAL ANS:
33     // for each node, we need calculate:
34     //  ans = max(ans,
35     //            root 
36     //                + max{help(root->left), 0}
37     //                + max{help(root->right), 0}
38     //         )
39 
40     int help(TreeNode* root, int& res) {
41         if(!root) return 0;
42         int l = max(0, help(root->left, res));
43         int r = max(0, help(root->right, res));
44         res = max(res, root->val + l + r);// real answer: root+l and r
45         return root->val + max(l, r);// recursion answer: root+l or r
46     }
47     int maxPathSum(TreeNode* root) {
48         if(!root) return 0;
49         int res = INT_MIN;
50         help(root, res);
51         return res;
52     }
53 };

543. Diameter of Binary Tree

问题：

求出给定二叉树中，最大路径（节点个数最多）。（至少包含树中一个节点）

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.

　　

解法：Binary Tree（二叉树）

同上题：

利用辅助函数help，进行递归：

求出，包含当前节点root，到单个子树的最大距离。

即，递归函数的返回值：1+max(l, r)

本题所求真正解为：

res= max( res, r+l ）

代码参考：

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 8  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 9  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10  * };
11  */
12 class Solution {
13 public:
14     int help(TreeNode* root, int& res) {
15         if(!root) return 0;
16         int l = help(root->left, res);
17         int r = help(root->right, res);
18         res = max(res, l+r);
19         return 1+max(l, r);
20     }
21     int diameterOfBinaryTree(TreeNode* root) {
22         if(!root) return 0;
23         int res = 0;
24         help(root, res);
25         return res;
26     }
27 };

687. Longest Univalue Path

问题：

求出给定二叉树中，最大相同节点的路径。（至少包含树中一个节点）

Example 1:
Input:
              5
             / 
            4   5
           /    
          1   1   5
Output: 2

Example 2:
Input:

              1
             / 
            4   5
           /    
          4   4   5
Output: 2

Note: The given binary tree has not more than 10000 nodes. The height of the tree is not more than 1000.

　　

解法：Binary Tree（二叉树）

同上题：

利用辅助函数help，进行递归：

求出，包含当前节点root，到单个子树的相同节点的最大路径。

  • if root->val == left->val：l++
    • else l=0
  • if root->val == right->val: r++
    • else r=0

即，递归函数的返回值：max(l, r)

本题所求真正解为：

res= max( res, r+l ）

代码参考：

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 8  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 9  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10  * };
11  */
12 class Solution {
13 public:
14     int help(TreeNode* root, int& res) {
15         if(!root) return 0;
16         int l = help(root->left, res);
17         int r = help(root->right, res);
18         if(root->left && root->val == root->left->val) {
19             l = l+1;
20         } else {
21             l = 0;
22         }
23         if(root->right && root->val == root->right->val) {
24             r = r+1;
25         } else {
26             r = 0;
27         }
28         res = max(res, l+r);
29         return max(l,r);
30     }
31     int longestUnivaluePath(TreeNode* root) {
32         if(!root) return 0;
33         int res = 0;
34         help(root, res);
35         return res;
36     }
37 };
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/habibah-chang/p/13766828.html