Leetcode 1305. All Elements in Two Binary Search Trees

Posted on |

问题描述:
Given two binary search trees root1 and root2.

Return a list containing all the integers from both trees sorted in ascending order.

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

思路1：首先想到的当然是一个先序遍历得到两个ascending数组，然后再合并两个ascending数组。
时间复杂度O(nlogk),空间复杂度为O(n+k)。

为了降低空间复杂度和申请的内存空间。先序遍历二叉树的结果就是将每一个最左子树的右子树展开，相连。
于是有了如下方案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    
    void pushLeft(stack<TreeNode*> &s, TreeNode* node){
        while(node){
            s.push(node);
            node = node->left;
        }
    }
    
    vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
        vector<int> ret;
        
        stack<TreeNode*> s1, s2;
        pushLeft(s1, root1);
        pushLeft(s2, root2);
        
        while(s1.size() || s2.size()){
            stack<TreeNode*> &s = !s1.size()?s2: !s2.size()? s1: s1.top()->val<s2.top()->val? s1:s2; //reference must be initialized
            // stack<TreeNode*> &s = s1;
            // if(!s1.size()){
            //     s = s2;
            // } else if(!s2.size()){
            //     s = s1;
            // } else{
            //     TreeNode* node1 = s1.top();
            //     TreeNode* node2 = s2.top();
            //     if(node1->val < node2->val) s = s1;
            //     else s = s2;
            // }
            
            TreeNode* node = s.top();
            s.pop();
            ret.push_back(node->val);
            pushLeft(s, node->right);
        }
        return ret;
        
    }
    
};

这里思路比较容易想明白，但是这里需要用到一个引用。
引用变量是一个别名，也就是说，它是某个已存在变量的另一个名字。一旦把引用初始化为某个变量，就可以使用该引用名称或变量名称来指向变量。

引用在声明的时候就必须初始化。

但是不知道为什么Java就可以 https://leetcode.com/problems/all-elements-in-two-binary-search-trees/discuss/465183/One-pass-O(n)-time-using-stack-(easy-to-understand)