654. 最大二叉树

最大值是根节点，找到根节点后递归构建

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return dfs(nums, 0, nums.size()); // 左闭右开
    }

    TreeNode* dfs(vector<int>& nums, int L, int R)
    {
        if (L >= R) return nullptr;
        // 找到当前的根节点
        int maxIdx = L;
        for (int i = L + 1; i < R; i ++)
        {
            if (nums[i] > nums[maxIdx])
            {
                maxIdx = i;
            }
        }

        TreeNode* root = new TreeNode(nums[maxIdx]);
        root->left = dfs(nums, L, maxIdx);
        root->right = dfs(nums, maxIdx + 1, R);

        return root;
    }
};

617. 合并二叉树

左左和右右，如果为空就空，要触发return条件

class Solution {
public:
    // 一起遍历
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        return dfs(root1, root2);
    }

    TreeNode* dfs(TreeNode* root1, TreeNode* root2)
    {
        if (root1 == nullptr && root2 == nullptr) return nullptr;
        // 当前节点相加
        TreeNode* root = new TreeNode(0);
        if (root1) root->val += root1->val;
        if (root2) root->val += root2->val;

        // 左左  右右
        TreeNode* p1 = root1;
        TreeNode* p2 = root2;
        if (root1) p1 = root1->left;
        if (root2) p2 = root2->left;
        // 左左
        root->left = dfs(p1, p2);

        // 右右
        p1 = root1;
        p2 = root2;
        if (root1) p1 = root1->right;
        if (root2) p2 = root2->right;
        root->right = dfs(p1, p2);

        return root;
    }
};

700. 二叉搜索树中的搜索

可以抓住二叉搜索树的特点：左小右大。
dfs的时候判断下方向即可。

class Solution {
public:
    int val;
    bool flag = false;
    TreeNode* res;
    TreeNode* searchBST(TreeNode* root, int val_) {
        val = val_;
        dfs(root);
        return res;
    }

    void dfs(TreeNode* root)
    {
        if (root == nullptr) return;
        if (flag) return;
        if (root->val == val) 
        {
            flag = true;
            res = root;
            return;
        }
        if(root->val > val) dfs(root->left);
        if(root->val < val) dfs(root->right);
    }
};

98. 验证二叉搜索树

中序遍历是有序的

class Solution {
public:
    vector<int> nums;
    bool isValidBST(TreeNode* root) {
        dfs(root);
        for (int i = 1; i < nums.size(); i ++)
        {
            if (nums[i] <= nums[i-1])
                return false;
        }
        return true;
    }

    void dfs(TreeNode* root)
    {
        if (root == nullptr) return;
        dfs(root->left);
        nums.push_back(root->val);
        dfs(root->right);
    }
};