Day20 构造二叉树，二叉搜索树

By HQWQF 2024/01/01

笔记

654.最大二叉树

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

1. 创建一个根节点，其值为 nums 中的最大值。
2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。

返回 nums* 构建的* 最大二叉树 。

输入： nums = [3,2,1,6,0,5]

输出：[6,3,5,null,2,0,null,null,1]

解释： 递归调用如下所示：

• [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
  • [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
    • 空数组，无子节点。
    • [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
      • 空数组，无子节点。
      • 只有一个元素，所以子节点是一个值为 1 的节点。
  • [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
    • 只有一个元素，所以子节点是一个值为 0 的节点。
    • 空数组，无子节点。

解法：递归法

很明显需要使用递归。参数是数组，终止条件可以设置为数组的大小，每个函数申请一个节点并让其左右指针指向下一层递归的返回值，然后函数向上一层返回一个节点。

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        if(nums.size() == 0){return nullptr;}
        int max = -1;
        int maxIndex = 0;
        for(int i = 0;i<nums.size();i++)
        {
            if(nums[i] > max){max = nums[i];maxIndex = i;}
        }
        TreeNode* root = new  TreeNode(max);
        vector<int> left(nums.begin(), nums.begin() + maxIndex);
        root->left = constructMaximumBinaryTree(left);
        vector<int> right(nums.begin() + maxIndex + 1,nums.end());
        root->right = constructMaximumBinaryTree(right);
        return root;
    }
};

由于每次递归都新建了数组，这个写法的时间和空间都不理想，我们可以将递归参数改成数组下标，用两个下标规定一个局部数组。

class Solution {
private:
    // 在左闭右开区间[left, right)，构造二叉树
    TreeNode* traversal(vector<int>& nums, int left, int right) {
        if (left >= right) return nullptr;
        // 分割点下标：maxValueIndex
        int maxValueIndex = left;
        for (int i = left + 1; i < right; ++i) {
            if (nums[i] > nums[maxValueIndex]) maxValueIndex = i;
        }
        TreeNode* root = new TreeNode(nums[maxValueIndex]);
        // 左闭右开：[left, maxValueIndex)
        root->left = traversal(nums, left, maxValueIndex);
        // 左闭右开：[maxValueIndex + 1, right)
        root->right = traversal(nums, maxValueIndex + 1, right);
        return root;
    }
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return traversal(nums, 0, nums.size());
    }
};

617.合并二叉树

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

示例 1：

输入： root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]输出：[3,4,5,5,4,null,7]

递归法

并没有什么难点，但是容易写出糟糕的代码：

递归法代码

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(root1 == nullptr && root2 == nullptr){return nullptr;}
        TreeNode* node = new TreeNode(0);
        TreeNode* next1;
        TreeNode* next2;
        if(root1 && root2)
        {
            node->val = root1->val +root2->val;
            node->left = mergeTrees(root1->left, root2->left);
            node->right = mergeTrees(root1->right, root2->right);
        }
        else if(root1)
        {
            node->val = root1->val;
            node->left = mergeTrees(root1->left, nullptr);
            node->right = mergeTrees(root1->right,nullptr);
        }
        else if(root2)
        {
            node->val = root2->val;
            node->left = mergeTrees(nullptr, root2->left);
            node->right = mergeTrees(nullptr,root2->right);
        }
        return node;
    }
};

简洁的代码：

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == NULL) return t2;
        if (t2 == NULL) return t1;
        // 重新定义新的节点，不修改原有两个树的结构
        TreeNode* root = new TreeNode(0);
        root->val = t1->val + t2->val;
        root->left = mergeTrees(t1->left, t2->left);
        root->right = mergeTrees(t1->right, t2->right);
        return root;
    }
};

对比发现，原来的代码可以优化的地方主要是在一边的树节点为null之后没必要用null继续递归，因为一边的树节点为null后可想而知着个空节点并不会有任何延续，所以这个位置接下来所有节点都是和另外一棵树的一样，所以直接连接上另外一棵树的对应节点就行。

注释

• 其实这也是为什么双向连接的链表、树在有些情况下很好用，我们还是会使用单向连接的原因：可以对某些节点进行共享或者是方便地进行扩展（扩展时不必连回去）。

迭代法

另外我们还可以在层序遍历的基础上，对正在遍历的节点进行判断就行

迭代法代码

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == NULL) return t2;
        if (t2 == NULL) return t1;
        queue<TreeNode*> que;
        que.push(t1);
        que.push(t2);
        while(!que.empty()) {
            TreeNode* node1 = que.front(); que.pop();
            TreeNode* node2 = que.front(); que.pop();
            // 此时两个节点一定不为空，val相加
            node1->val += node2->val;

            // 如果两棵树左节点都不为空，加入队列
            if (node1->left != NULL && node2->left != NULL) {
                que.push(node1->left);
                que.push(node2->left);
            }
            // 如果两棵树右节点都不为空，加入队列
            if (node1->right != NULL && node2->right != NULL) {
                que.push(node1->right);
                que.push(node2->right);
            }

            // 当t1的左节点 为空 t2左节点不为空，就赋值过去
            if (node1->left == NULL && node2->left != NULL) {
                node1->left = node2->left;
            }
            // 当t1的右节点 为空 t2右节点不为空，就赋值过去
            if (node1->right == NULL && node2->right != NULL) {
                node1->right = node2->right;
            }
        }
        return t1;
    }
};

700.二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

示例 1:

输入： root = [4,2,7,1,3], val = 2输出：[2,1,3]

我们先复习一下什么是二叉搜索树：

对于一个二叉搜索树的节点，若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

递归法

我们可以在遍历节点时进行大小的判断，节点值比当前的大就往右边找，节点值比比当前的大就往左边找。

递归法代码

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

迭代法

说起二叉树的迭代法我们可能会想到用用栈去模拟递归过程，但是实际上我们在二叉搜索树中只需要一路到底，二叉搜索树的有序性会指引我们的方向，没必要利用栈在走其他方向。

迭代法代码

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

98.验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

• 节点的左子树只包含 小于 当前节点的数。
• 节点的右子树只包含 大于 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

递归法，转化为数组

?️这里有个陷阱，我们不能比较左节点小于中间节点，右节点大于中间节点就完事了，而是要左子树所有节点小于中间节点，右子树所有节点大于中间节点。

对于二叉搜索树来说，只要中序遍历树，遍历到的节点的值一定是递增的，所以我们可以将中序遍历的结果保存为一个列表，然后判断其是否递增。

代码

class Solution {
private:
    vector<int> vec;
    void traversal(TreeNode* root) {
        if (root == NULL) return;
        traversal(root->left);
        vec.push_back(root->val); // 将二叉搜索树转换为有序数组
        traversal(root->right);
    }
public:
    bool isValidBST(TreeNode* root) {
        vec.clear(); // 不加这句在leetcode上也可以过，但最好加上
        traversal(root);
        for (int i = 1; i < vec.size(); i++) {
            // 注意要小于等于，搜索树里不能有相同元素
            if (vec[i] <= vec[i - 1]) return false;
        }
        return true;
    }
};

递归法

由于判断递增只需要当前元素和上一个元素，我们也可以通过保存上一个元素的方式直接在递归的过程中判断是否递增。

代码

class Solution {
public:
    TreeNode* pre = NULL; // 用来记录前一个节点
    bool isValidBST(TreeNode* root) {
        if (root == NULL) return true;
        bool left = isValidBST(root->left);

        if (pre != NULL && pre->val >= root->val) return false;
        pre = root; // 记录前一个节点

        bool right = isValidBST(root->right);
        return left && right;
    }
};

迭代法

同样的思想我们我们可以用到迭代法中：

迭代法代码

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        TreeNode* pre = NULL; // 记录前一个节点
        while (cur != NULL || !st.empty()) {
            if (cur != NULL) {
                st.push(cur);
                cur = cur->left;                // 左
            } else {
                cur = st.top();                 // 中
                st.pop();
                if (pre != NULL && cur->val <= pre->val)
                return false;
                pre = cur; //保存前一个访问的结点

                cur = cur->right;               // 右
            }
        }
        return true;
    }
};

本栏目推荐文章
• 2024/1/13 算法笔记
• 代码随想录 day18 找树左下角的值 路径总和 从中序与后序遍历序列构造二叉树
• Openharmony 跑 CV 算法
• .NET中的加密算法总结(自定义加密Helper类续)
• Scala编程语言day1
• 2024-1-13 DAY4
• 算法练习题
• 多路io复用epoll [补档-2023-07-20]
• 算法学习Day26组合总和、分割回文串
• （坚持每天写算法）基础算法复习与学习part1基础算法1-7——高精度减法（处理t=1和t>1代码的写法，t为操作次数）

算法 Day 20算法day 20 day 20 编辑器 漏洞day 20 part6 part day 20 8.20 day4 day 20 自动机 算法 笔记20 算法 字符openssl 20.1 算法openssl 20.2 rsa 算法openssl 20.3 aes 算法 动态part day