forked from KnowledgeCenterYoutube/LeetCode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path1305_All_Elements_in_Two_Binary_Search_Trees
126 lines (115 loc) · 3.56 KB
/
1305_All_Elements_in_Two_Binary_Search_Trees
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
Leetcode 1305: All Elements in Two Binary Search Trees
Detailed video explanation: https://youtu.be/B97Hk1H2x2s
======================================================
C++:
----
/**
* 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) {
stack<TreeNode *> S1, S2;
vector<int> result;
while(root1 || root2 || !S1.empty() || !S2.empty()){
while(root1){
S1.push(root1);
root1 = root1->left;
}
while(root2){
S2.push(root2);
root2 = root2->left;
}
if(S2.empty() || (!S1.empty() && S1.top()->val <= S2.top()->val)){
root1 = S1.top();
S1.pop();
result.push_back(root1->val);
root1 = root1->right;
} else {
root2 = S2.top();
S2.pop();
result.push_back(root2->val);
root2 = root2->right;
}
}
return result;
}
};
Java:
----
/**
* 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) {
Stack<TreeNode> S1 = new Stack(), S2 = new Stack();
List<Integer> result = new ArrayList();
while(root1 != null || root2 != null || !S1.empty() || !S2.empty()){
while(root1 != null){
S1.push(root1);
root1 = root1.left;
}
while(root2 != null){
S2.push(root2);
root2 = root2.left;
}
if(S2.empty() || (!S1.empty() && S1.peek().val <= S2.peek().val)){
root1 = S1.pop();
result.add(root1.val);
root1 = root1.right;
} else {
root2 = S2.pop();
result.add(root2.val);
root2 = root2.right;
}
}
return result;
}
}
Python3:
-------
# 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]:
S1, S2, result = [], [], []
while root1 != None or root2 != None or len(S1) > 0 or len(S2) > 0:
while root1 != None:
S1.append(root1)
root1 = root1.left
while root2 != None:
S2.append(root2)
root2 = root2.left
if len(S2) == 0 or (len(S1) > 0 and S1[-1].val <= S2[-1].val):
root1 = S1.pop()
result.append(root1.val)
root1 = root1.right
else:
root2 = S2.pop()
result.append(root2.val)
root2 = root2.right
return result;