代码随想录算法训练营打卡Day20 | LeetCode654 最大二叉树、LeetCode617 合并二叉树、LeetCode700 二叉搜索树中的搜索、LeetCode98 验证二叉搜索树

摘要

从序列构造二叉树的关键是要找到划分点，将序列分为左子树的序列和右子树的序列
在对二叉树进行访问前，要根据问题确定用哪种遍历方式进行访问
二叉搜索树的定义是左子树的所有节点的值小于根节点的值，右子树的所有节点的值小于根节点的值；是“左子树”和“右子树”，而不是“左孩子”和右孩子

LeetCode654 最大二叉树

654. 最大二叉树 - 力扣（Leetcode）

初见题目的想法，这道题与用中序序列和后序序列构造二叉树有异曲同工之妙，只是找划分节点的规则不同：
- 用中序序列和后序序列构造二叉树，是将后序序列的最后一个节点作为根节点，然后找到根节点在中序序列中的位置，将中序序列划分为左子树的序列和右子树的序列，再通过左、右子树的序列长度，在后序序列中划分出左子树的序列和右子树的序列。上述过程是递归的。
- 而本题定义的最大二叉树，找划分节点的规则变为了找序列中值最大的节点作为根节点，然后将序列划分为左子树的序列和右子树的序列，这个过程也是递归的。
明确了划分序列的过程，接下来就是写递归函数：
- 传入的参数和返回值：传入构造二叉树的序列，以及当前子树对应的区间的左边界和右边界，本题采用左闭右开区间。返回值为当前子树的根节点。
- 递归的终止条件：序列内没有节点，或序列内仅有一个节点（说明到达叶节点）
- 单层递归的逻辑：首先找到序列内值最大的节点，记录该节点在序列中的位置，并将其作为根节点；然后，以根节点为分界，将序列划分为左子树的序列和右子树的序列，尝试构造根节点的左子树和右子树。

完整的题解代码如下

class Solution {
public:
    TreeNode* construct(vector<int>& nums, int l, int r) {// [l, r)
        if (l >= r) return nullptr;
        if (r - l == 1) return new TreeNode(nums[l]);
        int maxVal = INT_MIN;
        int delim = 0;
        for (int i = l; i < r; i++) {
            if (nums[i] > maxVal) {
                maxVal = nums[i];
                delim = i;
            }
        }
        TreeNode* cur = new TreeNode(nums[delim]);
        cur->left = construct(nums, l, delim);
        cur->right = construct(nums, delim + 1, r);
        return cur;
    }
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return construct(nums, 0, nums.size());
    }
};

LeetCode617 合并二叉树

617. 合并二叉树 - 力扣（Leetcode）

初见题目的想法：这道题乍一看涉及同时访问两棵二叉树，但实际上同时访问的两棵二叉树的节点位置是相同的，所以逻辑上和访问一棵二叉树类似。
采用前序遍历来合并二叉树
- 传入的参数和返回值：传入两棵树位置”重叠的“节点，返回合并后的节点
- 递归的终止条件：两棵树在该位置的节点都为空
- 单层递归的的逻辑：首先合并当前位置的两个”重叠的”节点，然后尝试合并当前节点的左节点和右节点。

完整题解代码如下，

class Solution {
public:
    TreeNode* merge(TreeNode* cur1, TreeNode* cur2) {
        if (!cur1 && !cur2) return nullptr;
        if (cur1 && !cur2) return cur1;
        if (!cur1 && cur2) return cur2;

        TreeNode* mergedNode = new TreeNode(cur1->val + cur2->val);
        mergedNode->left = merge(cur1->left, cur2->left);
        mergedNode->right = merge(cur1->right, cur2->right);

        return mergedNode;
    }
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        return merge(root1, root2);
    }
};

需要注意的是，上面的题解代码还是没有完全构造一棵新的二叉树，直接return cur1或return cur2会让新的二叉树与旧的二叉树共享一些节点，所以可以做以下修改

class Solution {
public:
    TreeNode* merge(TreeNode* cur1, TreeNode* cur2) {
        if (!cur1 && !cur2) return nullptr;
        if (cur1 && !cur2) return new TreeNode(cur1->val, cur1->left, cur1->right);
        if (!cur1 && cur2) return new TreeNode(cur2->val, cur2->left, cur2->right);

        TreeNode* mergedNode = new TreeNode(cur1->val + cur2->val);
        mergedNode->left = merge(cur1->left, cur2->left);
        mergedNode->right = merge(cur1->right, cur2->right);

        return mergedNode;
    }
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        return merge(root1, root2);
    }
};

LeetCode700 二叉搜索树中的搜索

700. 二叉搜索树中的搜索 - 力扣（Leetcode）

二叉搜索树中的搜索非常直观，和二分搜索很相似：
- 若目标值比当前节点的值小，则去访问当前节点的左孩子；若目标值比当前节点的值大，则去访问当前节点的右孩子。
- 从根节点开始，重复上述步骤，直到找到目标值，或当前节点为空节点。

递归法

class Solution {
public:
    TreeNode* search(TreeNode* cur, int& val) {
        TreeNode* res = nullptr;
        // 短路判断，cur为空则直接返回，不会再判断cur->val == val，避免操作空指针
        if (!cur || cur->val == val) return cur;
        if (val < cur->val) res = search(cur->left, val);
        if (val > cur->val) res = search(cur->right, val);
        return res;
    }
    TreeNode* searchBST(TreeNode* root, int val) {
        return search(root, val);
    }
};

迭代法

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

LeetCode98 验证二叉搜索树

98. 验证二叉搜索树 - 力扣（Leetcode）

初见题目的想法，陷入了经典误区

class Solution {
public:
    bool isValid(TreeNode* cur) {
        if (cur->left && cur->right) {
            if (cur->left->val >= cur->val || cur->right->val <= cur->val) return false;
            else return isValid(cur->left) && isValid(cur->right); 
        }
        if (cur->left && !cur->right) {
            if (cur->left->val >= cur->val) return false;
            return isValid(cur->left);
        }
        if (!cur->left && cur->right) {
            if (cur->right->val <= cur->val) return false;
            return isValid(cur->right);
        }
        return true;
    }
    bool isValidBST(TreeNode* root) {
        if (!root) return true;
        else return isValid(root);
    }
};

为什么会错？这段代码的逻辑只能保证“左孩子的值小于父节点的值和右孩子的值大于父节点的值”，这只是局部的。而二叉搜索树要求的是“左子树所有节点的值小于父节点的值和右子树所有节点的值大于父节点的值。所以上面这段代码乍一看没什么问题，但是它是不符合二叉查找树的定义的。
下图就是反例。对于每个节点，其左孩子的都值都小于自己的值，右孩子的值都大于自己的值，但是这并不能保证左子树和右子树也符合要求。下图的节点3 就是问题所在，3 小于 6 没错，但是 3 也小于 5，3 实际上应该在 5 的左子树。下图所示的二叉树并不是一棵二叉查找树。

这不是二叉搜索树

再回顾一次二叉搜索树的定义，我开始思考应该用什么样的遍历方式更加合适
- 二叉搜索树是一个有序树：
  - 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  - 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  - 它的左、右子树也分别为二叉搜索树
- 二叉搜索树的定义，使得二叉搜索树的中序遍历序列一定是一个升序序列。
所以，只要在中序遍历的过程中，验证当前节点的值是否比中序遍历中上一个节点的值大即可
- 传入的参数和返回值：传入当前节点和上一个节点。返回当前子树是否为二叉搜索树。
- 递归的终止条件：当前节点为空，空树是一棵二叉搜索树，直接返回true；或者可以理解为空节点对是否是二叉搜索树没有影响，可以直接返回true。
- 单层递归的处理逻辑：要注意是中序遍历，所以先判断左子树是否是二叉搜索树，再判断当前节点的值是否大于上一个节点的值，然后再去判断右子树是否为二叉搜索树。

完整题解代码如下

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