[LeetCode] 1305. All Elements in Two Binary Search Trees #1305

grandyang · 2019-05-30T16:34:25Z

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 同步地址:

#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 题目讲解汇总(持续更新中...)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

喜欢请点赞，疼爱请打赏❤️~.~