合併兩個BST，並保留有限的空間

例

`4 5 6 7 9 13`

推薦碼

C ++代碼以有限的額外空間合併兩個BST

```#include <bits/stdc++.h>
using namespace std;
struct node
{
int data;
node *left;
node *right;
};

// returns a new node with supplied data
node* create(int data)
{
node *temp = new node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}

void inorder(node *root)
{
if(root){
inorder(root->left);
cout<<root->data<<" ";
inorder(root->right);
}
}

void merge(node *root1, node *root2)
{
stack<node*> s1;node* cur1 = root1;
stack<node*> s2;node* cur2 = root2;
//if first tree is empty, print second tree
if(!root1){
inorder(root2);
return;
}
// if second tree is empty, print first tree
if(!root2){
inorder(root2);
return;
}
// print the nodes which are not yet visited or visited but not printed
while(cur1 != NULL || !s1.empty() || cur2 != NULL || !s2.empty())
{
// iterative inorder
if(cur1 != NULL || cur2 != NULL)
{
// Reach the leftmost node of both BSTs and push ancestors of
// leftmost nodes to stack s1 and s2 respectively
if(cur1 != NULL)
{
s1.push(cur1);
cur1 = cur1->left;
}
if (cur2 != NULL)
{
s2.push(cur2);
cur2 = cur2->left;
}
}
else
{
// if anyone of the tree's current node becomes Null
// then we need to check if stack is empty
if(s1.empty())
{
while(!s2.empty())
{
cur2 = s2.top();s2.pop();
cur2->left = NULL;
inorder(cur2);
}
return;
}
if(s2.empty())
{
while(!s1.empty())
{
cur1 = s1.top();s1.pop();
cur1->left = NULL;
inorder(cur1);
}
return;
}

// compare elements at the top of both stacks
cur1 = s1.top();s1.pop();
cur2 = s2.top();s2.pop();

// print the smaller of the two and push the larger element into the corresponding stack
if(cur1->data < cur2->data)
{
cout<<cur1->data<<" ";
cur1 = cur1->right;
s2.push(cur2);
cur2 = NULL;
}
else
{
cout<<cur2->data<<" ";
cur2 = cur2->right;
s1.push(cur1);
cur1 = NULL;
}
}
}
}

int main()
{
node *root1 = NULL, *root2 = NULL;
//first tree
root1 = create(5);
root1->left = create(4);
root1->right = create(13);

//second tree
root2 = create(7);
root2->left = create(6);
root2->right = create(9);

// Print sorted nodes of both trees
merge(root1, root2);

return 0;
}
```
`4 5 6 7 9 13`

Java代碼以有限的額外空間合併兩個BST

```import java.util.*;
import java.lang.*;
import java.io.*;

class node{
int data;
node left;
node right;
}

class Tree{
static node root;
static int count;
static node create(int data){
node tmp = new node();
tmp.data = data;
tmp.left = null;
tmp.right = null;
return tmp;
}

static void inorder(node root)
{
if(root != null){
inorder(root.left);
System.out.print(root.data+" ");
inorder(root.right);
}
}

static void merge(node root1, node root2)
{
Stack<node> s1 = new Stack<>();node cur1 = root1;
Stack<node> s2 = new Stack<>();node cur2 = root2;
//if first tree is empty, print second tree
if(root1 == null){
inorder(root2);
return;
}
// if second tree is empty, print first tree
if(root2 == null){
inorder(root1);
return;
}
// print the nodes which are not yet visited or visited but not printed
while(cur1 != null || s1.empty() == false || cur2 != null || s2.empty() == false)
{
if(cur1 != null || cur2 != null)
{
// Reach the leftmost node of both BSTs and push ancestors of
// leftmost nodes to stack s1 and s2 respectively
if(cur1 != null)
{
s1.push(cur1);
cur1 = cur1.left;
}
if (cur2 != null)
{
s2.push(cur2);
cur2 = cur2.left;
}
}
else
{
// if anyone of the tree's current node becomes Null
// then we need to check if stack is empty
if(s1.empty() == true)
{
while (s2.empty() == false)
{
cur2 = s2.pop();
cur2.left = null;
inorder(cur2);
}
return ;
}
if(s2.empty() == true)
{
while (s1.empty() == false)
{
cur1 = s1.pop();
cur1.left = null;
inorder(cur1);
}
return ;
}

// compare elements at the top of both stacks
cur1 = s1.pop();
cur2 = s2.pop();

// print the smaller of the two and push the larger element into the corresponding stack
if (cur1.data < cur2.data)
{
System.out.print(cur1.data+" ");
cur1 = cur1.right;
s2.push(cur2);
cur2 = null;
}
else
{
System.out.print(cur2.data+" ");
cur2 = cur2.right;
s1.push(cur1);
cur1 = null;
}
}
}
}

public static void main(String[] args)
{
node root1 = null;
node root2 = null;
//first tree
root1 = create(5);
root1.left = create(4);
root1.right = create(13);

//second tree
root2 = create(7);
root2.left = create(6);
root2.right = create(9);

// Print sorted nodes of both trees
merge(root1, root2);
}

}
```
`4 5 6 7 9 13`

複雜度分析

時間複雜度

O（N + M）， 因為我們同時在兩棵樹上進行了有序遍歷。 在有序遍歷期間，我們從兩棵樹上遍歷了節點，因此得到了線性時間複雜度。

空間複雜度

O（N + M）， 正式而言，空間複雜度將是兩棵樹的高度之和。 但是在最壞的情況下，輸入可能是傾斜的樹，在這種情況下，高度將等於樹中的節點數。