1305. All Elements in Two Binary Search Trees

Given two binary search trees root1 and root2, return  a list containing all the integers from both trees sorted in ascending order.

Example 1:

Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]

Example 2:

Input: root1 = [1,null,8], root2 = [8,1]
Output: [1,1,8,8]

Constraints:

  • The number of nodes in each tree is in the range [0, 5000].
  • -10^5 <= Node.val <= 10^5

这道题给了两棵二叉搜索树,让返回一个包含所有结点值的子数组,并且是有序的。最简单暴力的方法就是分别遍历两棵树,然后把得到的结点值放到一个数组里,然后再对该数组排序,而且也能通过 OJ。用这种方法的话就没有利用到二叉搜索树的性质,用任意一种遍历顺序都可以,参见代码如下:

解法一:

class Solution {
public:
    vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
        vector<int> res;
        dfs(root1, res);
        dfs(root2, res);
        sort(res.begin(), res.end());
        return res;
    }
    void dfs(TreeNode* node, vector<int>& res) {
        if (!node) return;
        dfs(node->left, res);
        res.push_back(node->val);
        dfs(node->right, res);
    }
};

上面的解法并没有利用到二叉搜索树的性质,可能并不是面试官想要看见的解法。二叉搜索树具有左子结点值小于父结点值,小于右子结点的特点,所以用中序遍历得到的结点值是有序的。这里分别对 root1 和 root2 进行中序遍历,分别得到两个有序的数组,这样就可以通过 merge 数组方式来将两个有序数组合并成一个大的有序数组了,是线性的复杂度。下面的代码用的队列而不是数组,并没有太大的区别,参见代码如下:

解法二:

class Solution {
public:
    vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
        vector<int> res;
        queue<int> q1, q2;
        dfs(root1, q1);
        dfs(root2, q2);
        while (!q1.empty() || !q2.empty()) {
            if (q2.empty() || (!q1.empty() && q1.front() <= q2.front())) {
                res.push_back(q1.front());
                q1.pop();
            } else {
                res.push_back(q2.front());
                q2.pop();
            }
        }
        return res;
    }
    void dfs(TreeNode* node, queue<int>& q) {
        if (!node) return;
        dfs(node->left, q);
        q.push(node->val);
        dfs(node->right, q);
    }
};

之前两种解法都是递归的写法,再来看一种迭代的写法,还是用的中序遍历,不过此时是同时中序遍历两棵树,按照大小顺序将结点值加入到结果 res 中,保证了最终的结果是有序的。对于迭代的中序遍历写法最好也是要掌握的,需要用到栈来辅助,由于是同时遍历两棵树,所以这里用两个栈 st1 和 st2。循环到条件是只要 root1,root2,st1 和 st2 有任意一个不为空,中序遍历的顺序是左根右,所以首先要做的把当前结点下方的所有左子结点压入栈中,不停的对 root1 遍历,只要不为空,就将结点压入栈,然后更新为其左子结点。同理对 root2 进行相同的操作,接下俩判断若 st2 为空,说明当前要操作 st1 中的结点,或着若 st1 不为空(此时 st2 也不为空),且 st1 的栈顶结点值小于等于 st2 的栈顶结点值时,同样操作 st1 中的结点。否则操作 st2 中的结点,操作方法都是取出栈顶结点,将其值加入结果 res 中,然后更新为其右子结点即可,参见代码如下:

解法三:

class Solution {
public:
    vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
        vector<int> res;
        stack<TreeNode*> st1, st2;
        while (root1 || root2 || !st1.empty() || !st2.empty()) {
            while (root1) {
                st1.push(root1);
                root1 = root1->left;
            }
            while (root2) {
                st2.push(root2);
                root2 = root2->left;
            }
            if (st2.empty() || (!st1.empty() && st1.top()->val <= st2.top()->val)) {
                root1 = st1.top(); st1.pop();
                res.push_back(root1->val);
                root1 = root1->right;
            } else {
                root2 = st2.top(); st2.pop();
                res.push_back(root2->val);
                root2 = root2->right;
            }
        }
        return res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1305

参考资料:

https://leetcode.com/problems/all-elements-in-two-binary-search-trees/

https://leetcode.com/problems/all-elements-in-two-binary-search-trees/discuss/1719941/C%2B%2B-oror-Best-Explanation-oror-Naive-and-Optimal

https://leetcode.com/problems/all-elements-in-two-binary-search-trees/discuss/1720210/JavaC%2B%2BPython-A-very-very-detailed-EXPLANATION

LeetCode All in One 题目讲解汇总(持续更新中…)

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,快快加入吧~)

知识星球 喜欢请点赞,疼爱请打赏❤️.

微信打赏

|

Venmo 打赏


—|—


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation