Tree
Depth-First Search
Binary Search Tree
Binary Tree
Sorting
Description
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]
.
-105 <= Node.val <= 105
Solutions
Solution 1
Python3 Java C++ Go TypeScript Rust
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 # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution :
def getAllElements ( self , root1 : TreeNode , root2 : TreeNode ) -> List [ int ]:
def dfs ( root , t ):
if root is None :
return
dfs ( root . left , t )
t . append ( root . val )
dfs ( root . right , t )
def merge ( t1 , t2 ):
ans = []
i = j = 0
while i < len ( t1 ) and j < len ( t2 ):
if t1 [ i ] <= t2 [ j ]:
ans . append ( t1 [ i ])
i += 1
else :
ans . append ( t2 [ j ])
j += 1
while i < len ( t1 ):
ans . append ( t1 [ i ])
i += 1
while j < len ( t2 ):
ans . append ( t2 [ j ])
j += 1
return ans
t1 , t2 = [], []
dfs ( root1 , t1 )
dfs ( root2 , t2 )
return merge ( t1 , t2 )
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
42
43
44
45
46
47
48
49
50
51
52 /**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List < Integer > getAllElements ( TreeNode root1 , TreeNode root2 ) {
List < Integer > t1 = new ArrayList <> ();
List < Integer > t2 = new ArrayList <> ();
dfs ( root1 , t1 );
dfs ( root2 , t2 );
return merge ( t1 , t2 );
}
private void dfs ( TreeNode root , List < Integer > t ) {
if ( root == null ) {
return ;
}
dfs ( root . left , t );
t . add ( root . val );
dfs ( root . right , t );
}
private List < Integer > merge ( List < Integer > t1 , List < Integer > t2 ) {
List < Integer > ans = new ArrayList <> ();
int i = 0 , j = 0 ;
while ( i < t1 . size () && j < t2 . size ()) {
if ( t1 . get ( i ) <= t2 . get ( j )) {
ans . add ( t1 . get ( i ++ ));
} else {
ans . add ( t2 . get ( j ++ ));
}
}
while ( i < t1 . size ()) {
ans . add ( t1 . get ( i ++ ));
}
while ( j < t2 . size ()) {
ans . add ( t2 . get ( j ++ ));
}
return ans ;
}
}
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
42 /**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public :
vector < int > getAllElements ( TreeNode * root1 , TreeNode * root2 ) {
vector < int > t1 ;
vector < int > t2 ;
dfs ( root1 , t1 );
dfs ( root2 , t2 );
return merge ( t1 , t2 );
}
void dfs ( TreeNode * root , vector < int >& t ) {
if ( ! root ) return ;
dfs ( root -> left , t );
t . push_back ( root -> val );
dfs ( root -> right , t );
}
vector < int > merge ( vector < int >& t1 , vector < int >& t2 ) {
vector < int > ans ;
int i = 0 , j = 0 ;
while ( i < t1 . size () && j < t2 . size ()) {
if ( t1 [ i ] <= t2 [ j ])
ans . push_back ( t1 [ i ++ ]);
else
ans . push_back ( t2 [ j ++ ]);
}
while ( i < t1 . size ()) ans . push_back ( t1 [ i ++ ]);
while ( j < t2 . size ()) ans . push_back ( t2 [ j ++ ]);
return ans ;
}
};
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
42
43
44
45 /**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func getAllElements ( root1 * TreeNode , root2 * TreeNode ) [] int {
var dfs func ( root * TreeNode ) [] int
dfs = func ( root * TreeNode ) [] int {
if root == nil {
return [] int {}
}
left := dfs ( root . Left )
right := dfs ( root . Right )
left = append ( left , root . Val )
left = append ( left , right ... )
return left
}
merge := func ( t1 , t2 [] int ) [] int {
var ans [] int
i , j := 0 , 0
for i < len ( t1 ) && j < len ( t2 ) {
if t1 [ i ] <= t2 [ j ] {
ans = append ( ans , t1 [ i ])
i ++
} else {
ans = append ( ans , t2 [ j ])
j ++
}
}
for i < len ( t1 ) {
ans = append ( ans , t1 [ i ])
i ++
}
for j < len ( t2 ) {
ans = append ( ans , t2 [ j ])
j ++
}
return ans
}
t1 , t2 := dfs ( root1 ), dfs ( root2 )
return merge ( t1 , t2 )
}
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 /**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function getAllElements ( root1 : TreeNode | null , root2 : TreeNode | null ) : number [] {
const res = [];
const stacks = [[], []];
while ( root1 != null || stacks [ 0 ]. length !== 0 || root2 != null || stacks [ 1 ]. length !== 0 ) {
if ( root1 != null ) {
stacks [ 0 ]. push ( root1 );
root1 = root1 . left ;
} else if ( root2 != null ) {
stacks [ 1 ]. push ( root2 );
root2 = root2 . left ;
} else {
if (
( stacks [ 0 ][ stacks [ 0 ]. length - 1 ] ?? { val : Infinity }). val <
( stacks [ 1 ][ stacks [ 1 ]. length - 1 ] ?? { val : Infinity }). val
) {
const { val , right } = stacks [ 0 ]. pop ();
res . push ( val );
root1 = right ;
} else {
const { val , right } = stacks [ 1 ]. pop ();
res . push ( val );
root2 = right ;
}
}
}
return res ;
}
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61 // Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std :: cell :: RefCell ;
use std :: rc :: Rc ;
impl Solution {
pub fn get_all_elements (
root1 : Option < Rc < RefCell < TreeNode >>> ,
root2 : Option < Rc < RefCell < TreeNode >>> ,
) -> Vec < i32 > {
fn dfs ( root : & Option < Rc < RefCell < TreeNode >>> , t : & mut Vec < i32 > ) {
if let Some ( root ) = root {
dfs ( & root . borrow (). left , t );
t . push ( root . borrow (). val );
dfs ( & root . borrow (). right , t );
}
}
let mut t1 = Vec :: new ();
let mut t2 = Vec :: new ();
dfs ( & root1 , & mut t1 );
dfs ( & root2 , & mut t2 );
let mut ans = Vec :: new ();
let mut i = 0 ;
let mut j = 0 ;
while i < t1 . len () && j < t2 . len () {
if t1 [ i ] < t2 [ j ] {
ans . push ( t1 [ i ]);
i += 1 ;
} else {
ans . push ( t2 [ j ]);
j += 1 ;
}
}
while i < t1 . len () {
ans . push ( t1 [ i ]);
i += 1 ;
}
while j < t2 . len () {
ans . push ( t2 [ j ]);
j += 1 ;
}
ans
}
}