题目链接：二叉树中的最大路径和

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

方法一：递归

/**
 * 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 dfs(TreeNode* root,int &ans) {
        if (root == nullptr) return 0;
        int l_val = dfs(root->left,ans);
        int r_val = dfs(root->right,ans);
        ans = max(ans,l_val+r_val+root->val);
        return max(max(l_val,r_val) + root->val,0);
    }
    int maxPathSum(TreeNode* root) {
        int ans = INT_MIN;
        dfs(root,ans);
        return ans;
    }
};

题目链接：二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

方法一：递归

/**
 * 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 == NULL) return NULL;
        if (root == p || root == q) return root;
        TreeNode* left = lowestCommonAncestor(root->left,p,q);
        TreeNode* right = lowestCommonAncestor(root->right,p,q);

        if (left && right) return root;
        return left ? left : right;
    }
};

方法二：栈

/**
 * 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 == NULL) return NULL;
        unordered_map<TreeNode*,TreeNode*> parent;
        parent[root] = NULL;

        stack<TreeNode*> s;
        s.push(root);
        while (!parent.count(p) || !parent.count(q)) {
            TreeNode* cur = s.top();
            s.pop();
            if (cur->left) {
                parent[cur->left] = cur;
                s.push(cur->left);
            }
            if (cur->right) {
                parent[cur->right] = cur;
                s.push(cur->right);
            }
        }
        unordered_set<TreeNode*> se;
        while (p) {
            se.insert(p);
            p = parent[p];
        }
        while (!se.count(q)) {
            q = parent[q];
        }
        return q;
    }
};

题目链接：从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

方法一：递归

/**
 * 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:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (inorder.size() == 0) return nullptr;
        TreeNode* root = new TreeNode(preorder[0]);
        int mid = 0;
        while (mid < inorder.size() && inorder[mid] != preorder[0]) {
            mid++;
        }

        vector<int> leftIn(inorder.begin(), inorder.begin() + mid);
        vector<int> rightIn(inorder.begin() + mid + 1, inorder.end());

        vector<int> leftPre(preorder.begin() + 1, preorder.begin() + 1 + mid);
        vector<int> rightPre(preorder.begin() + 1 + mid, preorder.end());

        root->left = buildTree(leftPre,leftIn);
        root->right = buildTree(rightPre,rightIn);
        return root;
    }
};

题目链接：括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

方法一：递归

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        dfs("",n,n);
        return res;
    }
    vector<string> res;
    void dfs(const string& str,int left,int right) {
        if (left < 0 || left > right) return ;
        if (left == 0 && right == 0) {
            res.push_back(str);
            return ;
        }
        dfs(str + '(',left - 1,right);
        dfs(str + ')',left,right - 1);
    }
};

题目链接：路径总和 III

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

方法一：递归

class Solution {
public:
    int rootSum(TreeNode* root, long long targetSum) {
        if (!root) {
            return 0;
        }

        int ret = 0;
        if (root->val == targetSum) {
            ret++;
        } 

        ret += rootSum(root->left, targetSum - root->val);
        ret += rootSum(root->right, targetSum - root->val);
        return ret;
    }

    int pathSum(TreeNode* root, int targetSum) {
        if (!root) {
            return 0;
        }
        
        int ret = rootSum(root, targetSum);
        ret += pathSum(root->left, targetSum);
        ret += pathSum(root->right, targetSum);
        return ret;
    }
};