654.最大二叉树

构造二叉树都是前序遍历，套路就是返回条件是构造的依据数组没有元素或者只有一个元素（叶子节点），从构造数组中取一个元素（依据题意，比如最大值，后序最后一个）作为节点，并以此节点作为分割边界分割构造数组，并将这个节点的左右节点指向左右分割子区间的递归结果，先处理当前节点，再左右，前序在遍历时构造节点，在遍历完返回的时候进行节点的连接，中序后序做不到。

//C++ 没看题解一遍过，棒
class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return doit(nums);
    }
    TreeNode* doit(vector<int> num) {
        if (num.size() == 0) return nullptr;
        int val = FindMax(num);
        TreeNode* cur = new TreeNode(val);
        if (num.size() == 1) return cur;
        int index;
        for (index = 0; index < num.size(); index++) {
            if (num[index] == val) break;
        }
        vector<int> left(num.begin(), num.begin() + index);
        vector<int> right(num.begin() + index + 1, num.end());
        cur->left = doit(left);
        cur->right = doit(right);
        return cur;

    }
    int FindMax(vector<int> num) {
        int max = INT_MIN;
        for (int i = 0; i < num.size(); i++) {
            if (num[i] > max) max = num[i];
        }
        return max;
    }
};

C#无开辟数组精简版，注意下寻找最大值的时候区间也要按照left,right搜，代随优化版也是这么做的。

alt


public class Solution {
    public TreeNode ConstructMaximumBinaryTree(int[] nums) {
        return doit(nums, 0, nums.Length);
    }
    public TreeNode doit(int[] nums, int left, int right) {
        if (left == right) return null;
        int val = int.MinValue;
        int index = 0;
        for (int i = left; i < right; i++) {
            if (nums[i] > val) {
                val = nums[i];
                index = i;
            }
        }
        Console.WriteLine(val);
        TreeNode cur = new TreeNode(val);
        if (right - left == 1) return cur;
        int leftBegin = left;
        int leftEnd = index;
        int rightBegin = index + 1;
        int rightEnd = right;
        Console.WriteLine("left: ["+ leftBegin + "," +leftEnd + ")");
        Console.WriteLine("right: [" + rightBegin + "," +rightEnd + ")");
        cur.left = doit(nums, leftBegin, leftEnd);
        cur.right = doit(nums, rightBegin, rightEnd);
        return cur;

    }
}

617.合并二叉树

自己的想法：递归三部曲，返回构造的节点，参数是不断遍历的两个依据树，当两个树都为空，遍历结束，其中一个树的节点不为空另一个树为空，则将不为空的树的节点作为新节点，递归向下。都不为空取和，递归向下。

//C#没看题解，自己写的
public class Solution {
    public TreeNode MergeTrees(TreeNode root1, TreeNode root2) {
        TreeNode cur;
        if (root1 == null && root2 == null) return null;
        if (root1 == null && root2 != null) {
            cur = new TreeNode(root2.val);
            cur.left = MergeTrees(root1, root2.left);
            cur.right = MergeTrees(root1, root2.right);
            return cur;
        }
        if (root1 != null && root2 == null) {
            cur = new TreeNode(root1.val);
            cur.left = MergeTrees(root1.left, root2);
            cur.right = MergeTrees(root1.right, root2);
            return cur;
        } 
        cur = new TreeNode(root1.val + root2.val);
        cur.left = MergeTrees(root1.left, root2.left);
        cur.right = MergeTrees(root1.right,root2.right);
        return cur;
    }

}

自己想的第一版里其实有两点可以精简，首先返回条件可以精简为两行，只要有一个为空，就返回另一个，另一个为空返回null也是合理的。其次只要有一个为空，其实不需要再对另一个不为空的做递归了，直接把这个节点连到当前节点上就相当于把一片的树都连了过来，所以也不需要单独Mergetrees了。

//C++ 精简版
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if (root1 == nullptr) return root2;
        if (root2 == nullptr) return root1;

        TreeNode* cur = new TreeNode(root1->val + root2->val);
        cur->left = mergeTrees(root1->left, root2->left);
        cur->right = mergeTrees(root1->right, root2->right);
        return cur;
    }
};

700.二叉搜索树中的搜索

自己的想法：二叉树左子比当前节点小，右子比当前节点大，所以搜索根据判断只走一边就行，找到元素返回，否则返回继续向下的结果直到空节点，需要深入理解一下return下一层搜索结果这种层层往上的思想。有返回的递归一定要接住。

alt

//C++ 一遍过自己写的
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (root == nullptr) return nullptr;
        if (val > root->val) {
            return searchBST(root->right, val);
        }
        else if (val < root->val) {
            return searchBST(root->left, val);
        }
        return root;

    }
};

层序方法剪个叉。

//C#
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        queue<TreeNode*> que;
        if (root == nullptr) return nullptr;
        que.push(root);
        while (!que.empty()) {
            int size = que.size();
            while (size--) {
                TreeNode* cur = que.front();
                que.pop();
                if (cur->val > val) {
                    if (cur->left != nullptr) que.push(cur->left);
                }
                else if (cur->val < val) {
                    if (cur->right != nullptr) que.push(cur->right);
                } else {
                    return cur;
                }
            }
        }
        return nullptr;
    }
};

由于二叉搜索树的特性，从上往下迭代搜索可以更简单。

//C++
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        while (root != nullptr) {
            if (root->val > val) root = root->left;
            else if (root->val < val) root = root->right;
            else return root;
        }
        return nullptr;
    }
};

98.验证二叉搜索树

二叉搜索树有个性质，中序遍历是个递增序列，由此只要中序遍历的节点值递增就是二叉搜索树，不用数组存也不用数值记，直接拿前驱节点比，这样避免溢出和开辟额外空间。


class Solution {
public:
    TreeNode* pre = nullptr;
    bool isValidBST(TreeNode* root) {
        if (root == nullptr) return true;
        bool isLeft = isValidBST(root->left);
        if (pre != nullptr && root->val <= pre->val) return false;
        pre = root;
        bool isRight = isValidBST(root->right);
        return isLeft && isRight;
    }
};

[代码随想录一刷] day20 二叉树

654.最大二叉树

617.合并二叉树

700.二叉搜索树中的搜索

98.验证二叉搜索树