236. 二叉樹的最近公共祖先 - 力扣（LeetCode）

dfs統計根節點到p，q節點的路徑，兩條路徑中最后一個相同節點就是公共祖先

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:bool dfs(TreeNode *root, TreeNode *p, vector<TreeNode*> &pp) {if (root == nullptr) return false;pp.push_back(root);if (root == p) return true;if (dfs(root->left, p, pp)) return true;if (dfs(root->right, p, pp)) return true;pp.pop_back();return false;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {vector<TreeNode*> p1, p2;dfs(root, p, p1), dfs(root, q, p2);int i, j;for (i = 0, j = 0; i < p1.size() && j < p2.size(); ++ i, ++ j) {if (p1[i] != p2[j]) break;}return p1[i - 1];}
};

---

124. 二叉樹中的最大路徑和 - 力扣（LeetCode）

每次遞歸判斷：以當前節點為起點的最長路徑，需要先判斷以左右子節點為根節點的最長路徑（可能為0，表示路徑中沒有節點），然后加上當前節點值
同時維護“經過當前節點的最長路徑”

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int ans = INT_MIN;int dfs(TreeNode* root) {if (root == nullptr) return 0;int lv = max(0, dfs(root->left));int rv = max(0, dfs(root->right));int cv = root->val + lv + rv;ans = max(ans, cv);return root->val + max(lv, rv);}int maxPathSum(TreeNode* root) {dfs(root);return ans;}
};