递归法解二叉树问题分类
不需要构造辅助函数
需要构造辅助函数
二叉树路径问题
问题分类
自顶向下
非自顶向下

递归法解二叉树问题分类

不需要构造辅助函数。
这种问题分为两类，一类是单树问题，且不需要用到子树的某一部分，或判断子树中存在某种性质，只要判断根节点左右子树的某些性质。
第二种是双树问题，即本身题目要求比较两棵树，两棵树的比较都只与其根节点有关
需要构造辅助函数。
这类题目通常只用根节点左右子树的性质无法完全解决问题，必须要判断其子树是否也满足某些性质才能够解题，即要调用辅助函数比较两个部分子树

不需要构造辅助函数

leetcode.100 相同的树

链接https://leetcode.cn/problems/same-tree/submissions/
解题思路：
递归函数功能：判断 p，q 两颗树是否相同
1. 递归终止条件：
  两棵树都不存在，则说明是相同的树
  两棵树只有一个存在，则说明不是相同的树
2. 递归返回值：返回两个树相同的条件
  根节点值相同
  左子树相同
  右子树相同
leetcode解题代码

/**
 * 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:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (!p && !q) return true;
        if (!p || !q) return false;

        return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

leetcode.104 二叉树的最大深度

链接https://leetcode.cn/problems/maximum-depth-of-binary-tree/
解题思路：
递归函数功能：计算以 root 为根节点的二叉树最大深度，返回最大深度
1. 递归终止条件：
  根节点不存在最大深度为 0
2. 递归返回值：返回二叉树的最大深度
  左子树最大深度和右子树最大深度取 max + 根节点的深度
leetcode解题代码

/**
 * 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 maxDepth(TreeNode* root) {
        if (!root) return 0;

        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

leetcode.559 N 叉树的最大深度

链接https://leetcode.cn/problems/maximum-depth-of-n-ary-tree/
解题思路：与上一题类似
leetcode解题代码

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    int maxDepth(Node* root) {
        if (!root) return 0;

        int res = 0;
        for (auto c: root->children)
            res = max(maxDepth(c), res);
        return res + 1;
    }
};

leetcode.965 单值二叉树

链接https://leetcode.cn/problems/univalued-binary-tree/
解题思路：
递归函数功能：判断二叉树是否为单值二叉树
1. 递归终止条件：
  空树是单值二叉树
  如果存在左儿子且左儿子的值和根节点的值不相等则不是单值二叉树
  如果存在右儿子且右儿子的值和根节点的值不相等则不是单值二叉树
2. 递归返回值：返回满足单值二叉树的条件
  左子树和右子树都是单值二叉树
leetcode解题代码

/**
 * 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:
    bool isUnivalTree(TreeNode* root) {
        if (!root) return true;
        if (root->left && root->left->val != root->val)
            return false;
        if (root->right && root->right->val != root->val)
            return false;

        return isUnivalTree(root->left) && isUnivalTree(root->right);
    }
};

leetcode.111 二叉树的最小深度

链接https://leetcode.cn/problems/minimum-depth-of-binary-tree/
解题思路：
递归函数功能：计算以 root 为根节点的二叉树最小深度，返回最小深度
1. 递归终止条件：
  空树最小深度为 0
  如果只有根节点最小深度为 1
  如果存在左儿子和右儿子，最小深度为左子树和右子树的最小深度 +1
  如果不存在左儿子，最小深度为右子树深度 +1
2. 递归返回值：返回二叉树的最小深度
  如果不存在右儿子，最小深度为左子树深度 +1
leetcode解题代码

/**
 * 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 minDepth(TreeNode* root) {
        if (!root) return 0;
        if (!root->left && !root->right) return 1;
        if (root->left && root->right)
            return min(minDepth(root->left), minDepth(root->right)) + 1;
        if (!root->left) return minDepth(root->right) + 1;

        return minDepth(root->left) + 1;
    }
};

leetcode.222 完全二叉树的节点个数

链接https://leetcode.cn/problems/count-complete-tree-nodes/
解题思路：
递归函数功能：计算以 root 为根节点的完全二叉树的节点个数，返回节点个数
1. 递归终止条件：
  空树节点个数为 0
2. 递归返回值：返回完全二叉树的节点个数
  左子树节点个数 + 右子树节点个数 +1
leetcode解题代码

/**
 * 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 countNodes(TreeNode* root) {
        if (!root) return 0;

        return countNodes(root->left) + countNodes(root->right) + 1;
    }
};

leetcode.404 左叶子之和

链接https://leetcode.cn/problems/sum-of-left-leaves/
解题思路：
递归函数功能：计算以 root 为根节点的二叉树的左叶子节点之和
1. 递归终止条件：
  根节点不存在，左叶子之和为 0
  只有根节点，左叶子之和为 0
2. 递归逻辑：
  如果节点存在左儿子并且左儿子为叶子节点，更新答案
  计算左子树的左叶子之和
  计算右子树的左叶子之和
3. 递归返回值：返回答案
leetcode解题代码

/**
 * 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 res = 0;
    int sumOfLeftLeaves(TreeNode* root) {
        if (!root) return 0;
        if (!root->left && !root->right) return 0;

        if (root->left && !root->left->left && !root->left->right)
            res += root->left->val;
        sumOfLeftLeaves(root->left);
        sumOfLeftLeaves(root->right);
        return res;
    }
};

leetcode.236 二叉树的最近公共祖先

链接https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
解题思路：
递归函数功能：找 p，q 两个节点的最近公共祖先节点
1. 递归终止条件：
  如果根节点不存在或 p，q 两个节点其中一个是根节点，那么最近公共祖先就是根节点
2. 递归逻辑：
  在左子树中找 p，q 的最近公共祖先，记为 l
  在右子树中找 p，q 的最近公共祖先，记为 r
  如果 l，r 都存在，说明 p，q 两个节点一个在左子树一个在右子树，最近公共祖先为根节点
  如果 l 不存在，最近公共祖先为 r，否则为 l
leetcode解题代码

/**
 * 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:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root || root == p || root == q) return root;

        auto l = lowestCommonAncestor(root->left, p, q);
        auto r = lowestCommonAncestor(root->right, p, q);
        if (l && r) return root;
        if (!l) return r;
        return l;
    }
};

需要构造辅助函数

leetcode.101 对称二叉树

链接https://leetcode.cn/problems/symmetric-tree/
解题思路：
主函数功能：判断以 root 为根节点的二叉树是否对称，返回对称二叉树的条件（需要近一步判断左右子树是否对称（辅助函数））
辅助函数功能：判断左右子树 p，q 是否对称

主函数：
1. 递归终止条件：
  如果根节点不存在，是对称二叉树
2. 递归返回值：对称二叉树的条件
  左右子树对称
辅助函数：
1. 递归终止条件：
  左右子树根节点 p，q 都不存在，则对称
  左右子树根节点只有一个存在，则不对称
2. 递归返回值：左右子树对称的条件
  根节点值相等
  p 的左子树和 q 的右子树对称
  p 的右子树和 q 的左子树对称
leetcode解题代码

/**
 * 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:
    bool isSymmetric(TreeNode* root) {
        if (!root) return true;

        return dfs(root->left, root->right);
    }

    bool dfs(TreeNode* p, TreeNode* q){
        if (!p && !q) return true;
        if (!p || !q) return false;

        return p->val == q->val && dfs(p->left, q->right) && dfs(p->right, q->left);
    }
};

leetcode.110 平衡二叉树

链接https://leetcode.cn/problems/balanced-binary-tree/
解题思路：
主函数功能：判断以 root 为根节点的二叉树是否平衡，返回平衡二叉树的条件（左右子树最大高度差 <=1（辅助函数），左子树是平衡二叉树，右子树是平衡二叉树）
辅助函数功能：求左右子树的最大高度

主函数：
1. 递归终止条件：
  如果根节点不存在，是平衡二叉树
2. 递归返回值：平衡二叉树的条件
  左右子树最大高度差 <=1
  左子树是平衡二叉树
  右子树是平衡二叉树
辅助函数：
1. 递归终止条件：
  根节点不存在最大高度为 0
2. 递归返回值：左右子树的最大高度
  左子树最大高度和右子树最大高度取 max +1
leetcode解题代码

/**
 * 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:
    bool isBalanced(TreeNode* root) {
        if (!root) return true;

        return abs(dfs(root->left) - dfs(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
    }

    int dfs(TreeNode* root){
        if (!root) return 0;

        return max(dfs(root->left), dfs(root->right)) + 1;
    }
};

leetcode.572 另一棵树的子树

链接https://leetcode.cn/problems/subtree-of-another-tree/
解题思路：
主函数功能：判断以 subroot 为根节点的二叉树是否是以 root 为根节点的二叉树的子树，返回是子树的条件（两棵树相同（辅助函数）或是 root 左子树的子树或是 root 右子树的子树）
辅助函数功能：判断两棵树是否相同

主函数：
1. 递归终止条件：
  任何树都不是空树的子树
  空树是任何树的子树
2. 递归返回值：返回是子树的条件
  两棵树相同
  是 root 左子树的子树
  是 root 右子树的子树
辅助函数：
1. 递归终止条件：
  根节点都不存在，则两棵树相同
  根节点只有一个存在，则两棵树不相同
  根节点都存在但是值不相同，则两棵树不相同
2. 递归返回值：两棵树相同的条件
  左子树相同且右子树相同
leetcode解题代码

/**
 * 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:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if (!root) return false;
        if (!subRoot) return true;

        return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot) || dfs(root, subRoot);
    }

    bool dfs(TreeNode* p, TreeNode* q){
        if (!p && !q) return true;
        if (!p || !q) return false;
        if (p && q && p->val != q->val) return false;

        return dfs(p->left, q->left) && dfs(p->right, q->right);
    }
};

二叉树路径问题

问题分类

自顶向下：
从某一个节点(不一定是根节点)，从上向下寻找路径，到某一个节点(不一定是叶节点)结束
非自顶向下：
从任意节点到任意节点的路径，不需要从上到下寻找路径

自顶向下

leetcode.257 二叉树的所有路径

链接https://leetcode.cn/problems/binary-tree-paths/
解题思路：
递归函数功能：记录满足条件的路径
1. 递归终止条件：
  当前节点不存在则终止递归
  如果当前节点是叶子节点，说明找到了一条路径，将其加入答案并终止递归
2. 递归思路：
  当前节点存在，则将其加入路径
  递归搜索当前节点的左右子树，记录满足条件的路径
leetcode解题代码

/**
 * 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:
    vector<string> res; 
    vector<string> binaryTreePaths(TreeNode* root) {
        // 从根节点开始找所有满足条件的路径，初始路径为空
        dfs(root, "");
        return res;
    }
    // 记录满足条件的路径
    void dfs(TreeNode* cur, string path){
        if (!cur) return;

        path += to_string(cur->val);

        if (!cur->left && !cur->right){
            res.push_back(path);
            return;
        }
        dfs(cur->left, path + "->");
        dfs(cur->right, path + "->");
    }
};

leetcode.113 路径总和 II

链接https://leetcode.cn/problems/path-sum-ii/
解题思路：与上一题类似
leetcode解题代码

/**
 * 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:
    vector<vector<int>> res;
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<int> path;
        dfs(root, targetSum, path);
        return res;
    }

    void dfs(TreeNode* cur, int targetSum, vector<int> path){
        if (!cur) return;

        targetSum -= cur->val;
        path.push_back(cur->val);
        if (!cur->left && !cur->right && !targetSum){
            res.push_back(path);
            return;
        }

        dfs(cur->left, targetSum, path);
        dfs(cur->right, targetSum, path);
    }
};

leetcode.437 路径总和 III

链接https://leetcode.cn/problems/path-sum-iii/
解题思路：
主函数功能：计算整棵树总和为 targetSum 的路径数（左子树为起点的路径数 + 右子树为起点的路径数 + 根节点为起点的路径数（辅助函数））
辅助函数功能：计算以根节点为起点，总和为 targetSum 的路径数

主函数：
1. 递归终止条件：
  根节点不存在，路径数为 0
2. 递归逻辑：
  计算左子树为起点的路径数
  计算右子树为起点的路径数
  根节点为起点的路径数
3. 递归返回值：返回总路径数 res
辅助函数：
1. 递归终止条件：
  根节点不存在，路径数为 0
2. 递归逻辑：
  根节点存在并且目标值为 0，说明找到了一条路径 res+1
  递归左右子树找符合条件的路径
leetcode解题代码

/**
 * 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 res = 0;
    int pathSum(TreeNode* root, int targetSum) {
        if (!root) return 0;

        dfs(root, targetSum);
        pathSum(root->left, targetSum);
        pathSum(root->right, targetSum);

        return res;
    }

    void dfs(TreeNode* root, long targetSum){
        if (!root) return;

        targetSum -= root->val;
        if (!targetSum)
            res ++;
        dfs(root->left, targetSum);
        dfs(root->right, targetSum);
    }
};

非自顶向下

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

链接https://leetcode.cn/problems/binary-tree-maximum-path-sum/
解题思路：
递归函数功能：记录最大路径和，返回当前节点的最大路径和
1. 递归终止条件：
  当前节点不存在则最大路径和为 0
2. 递归逻辑：
  当前节点的最大路径和可以划分成左右子树两部分，两部分互不影响
  如果最大路径和为负数则不走这部分
  答案记录当前节点的最大路径和
3. 返回值：将当前节点的最大路径和返回
  在其它节点接收当前节点的最大路径和时，只会接收当前节点左右子树最大的那一部分
leetcode解题代码

/**
 * 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 res = INT_MIN;
    int maxPathSum(TreeNode* root) {
        // 从根节点开始计算最大路径
        dfs(root);
        return res;
    }
    // 计算最大路径和
    int dfs(TreeNode* cur){
        if (!cur) return 0;

        // 如果路径为负数将其置为 0（不走这条路）
        int l = max(0, dfs(cur->left));
        int r = max(0, dfs(cur->right));
        res = max(res, l + r + cur->val);

        // 当前节点能够提供给其它节点的最大路径和只能取左右子树的最大值
        return cur->val + max(l, r);
    }
};

leetcode.687 最长同值路径

链接https://leetcode.cn/problems/longest-univalue-path/
解题思路：与上一题类似
leetcode解题代码

/**
 * 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 res = INT_MIN;
    int longestUnivaluePath(TreeNode* root) {
        if (!root) return 0;
        // 从根节点开始计算
        dfs(root);
        return res;
    }
    // 计算当前节点的最长同值路径
    int dfs(TreeNode* cur){
        if (!cur) return 0;

        int l = dfs(cur->left);
        int r = dfs(cur->right);
        if (cur->left && cur->val == cur->left->val)
            l ++;
        else l = 0;
        if (cur->right && cur->val == cur->right->val)
            r ++;
        else r = 0;
        res = max(res, l + r);
        // 当前节点能够提供给其它节点的最长同值路径只能取左右子树的最大值
        return max(l, r);
    }
};

leetcode.543 二叉树的直径

链接https://leetcode.cn/problems/diameter-of-binary-tree/
与上一题类似
leetcode解题代码

/**
 * 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 res = INT_MIN;
    int diameterOfBinaryTree(TreeNode* root) {
        if (!root) return 0;
        
        dfs(root);
        return res;
    }

    int dfs(TreeNode* cur){
        if (!cur) return 0;

        int l = dfs(cur->left);
        int r = dfs(cur->right);
        if (cur->left) l ++;
        else l = 0;
        if (cur->right) r ++;
        else r = 0;
        res = max(res, l + r);

        return max(l, r);
    }
};

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

二叉树的递归方法.md

二叉树的递归方法.md

递归法解二叉树问题分类

不需要构造辅助函数

leetcode.100 相同的树

leetcode.104 二叉树的最大深度

leetcode.559 N 叉树的最大深度

leetcode.965 单值二叉树

leetcode.111 二叉树的最小深度

leetcode.222 完全二叉树的节点个数

leetcode.404 左叶子之和

leetcode.236 二叉树的最近公共祖先

需要构造辅助函数

leetcode.101 对称二叉树

leetcode.110 平衡二叉树

leetcode.572 另一棵树的子树

二叉树路径问题

问题分类

自顶向下

leetcode.257 二叉树的所有路径

leetcode.113 路径总和 II

leetcode.437 路径总和 III

非自顶向下

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

leetcode.687 最长同值路径

leetcode.543 二叉树的直径

Files

二叉树的递归方法.md

Latest commit

History

二叉树的递归方法.md

File metadata and controls

递归法解二叉树问题分类

不需要构造辅助函数

leetcode.100 相同的树

leetcode.104 二叉树的最大深度

leetcode.559 N 叉树的最大深度

leetcode.965 单值二叉树

leetcode.111 二叉树的最小深度

leetcode.222 完全二叉树的节点个数

leetcode.404 左叶子之和

leetcode.236 二叉树的最近公共祖先

需要构造辅助函数

leetcode.101 对称二叉树

leetcode.110 平衡二叉树

leetcode.572 另一棵树的子树

二叉树路径问题

问题分类

自顶向下

leetcode.257 二叉树的所有路径

leetcode.113 路径总和 II

leetcode.437 路径总和 III

非自顶向下

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

leetcode.687 最长同值路径

leetcode.543 二叉树的直径