[leetcode题解]1305. All Elements in Two Binary Search Trees

给你 root1 和 root2 这两棵二叉搜索树。

请你返回一个列表,其中包含 两棵树 中的所有整数并按 升序 排序。.

输入:root1 = [2,1,4], root2 = [1,0,3]
输出:[0,1,1,2,3,4]
示例 2:

输入:root1 = [0,-10,10], root2 = [5,1,7,0,2]
输出:[-10,0,0,1,2,5,7,10]
示例 3:

输入:root1 = [], root2 = [5,1,7,0,2]
输出:[0,1,2,5,7]
示例 4:

输入:root1 = [0,-10,10], root2 = []
输出:[-10,0,10]
示例 5:

输入:root1 = [1,null,8], root2 = [8,1]
输出:[1,1,8,8]
 
每棵树最多有 5000 个节点。
每个节点的值在 [-10^5, 10^5] 之间。

题目中给定两棵二叉搜索树,要求这两棵树种所有元素的顺序排列。

二叉搜索树的特点:根的左子树所有元素都小于等于根节点的元素,根的右子树中所有元素都大于等于根节点。

所以对于一个二叉搜索树,其中根遍历序列为有序数列。

本题暂时没有想到很好的方法,就使用比较笨的方法,用中根遍历分别遍历两棵子树,有序数列存入数组a,和b。

然后在a和b两个有序数组进行一个排列即可。

两个有序数组进行有序合并可以使用双指针的方法进行搞定。

总体的思路直接看代码,相对来说比较简单。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
#define MAX 100002

class Solution {
public:
    vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
        vector<int> ra;
        vector<int> rb;
        vector<int> res;
        int lena, lenb, len;
        int numa, numb;
        int la, lb;

        dfs(root1, ra);
        dfs(root2, rb);

        lena = ra.size();
        lenb = rb.size();
        la = lb = 0;
        while (la < lena || lb < lenb) {
            numa = numb = MAX;
            if (la < lena) {
                numa = ra[la];
            }

            if (lb < lenb) {
                numb = rb[lb];
            }

            if (numa < numb) {
                res.push_back(numa);
                ++la;
            } else {
                res.push_back(numb);
                ++lb;
            }
        }
        return res;
    }
private:
    void dfs(TreeNode *root, vector<int> &res)
    {
        if (root == NULL) {
            return;
        }

        dfs(root->left, res);
        res.push_back(root->val);
        dfs(root->right, res);
    }
};

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解]1305. All Elements in Two Binary Search Trees

本文链接地址:https://www.iaccepted.net/algorithm/leetcode/228.html

相关文章