-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy path1305-AllElementsInTwoBinarySearchTrees.cs
62 lines (57 loc) · 2.03 KB
/
1305-AllElementsInTwoBinarySearchTrees.cs
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
//-----------------------------------------------------------------------------
// Runtime: 360ms
// Memory Usage: 49.2 MB
// Link: https://leetcode.com/submissions/detail/391562509/
//-----------------------------------------------------------------------------
using System.Collections.Generic;
namespace LeetCode
{
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class _1305_AllElementsInTwoBinarySearchTrees
{
public IList<int> GetAllElements(TreeNode root1, TreeNode root2)
{
var stack1 = new Stack<TreeNode>();
var stack2 = new Stack<TreeNode>();
var result = new List<int>();
while (root1 != null || root2 != null || stack1.Count > 0 || stack2.Count > 0)
{
while (root1 != null)
{
stack1.Push(root1);
root1 = root1.left;
}
while (root2 != null)
{
stack2.Push(root2);
root2 = root2.left;
}
if ((stack2.Count == 0 && stack1.Count > 0) || (stack2.Count > 0 && stack1.Count > 0 && stack1.Peek().val <= stack2.Peek().val))
{
root1 = stack1.Pop();
result.Add(root1.val);
root1 = root1.right;
}
else if ((stack1.Count == 0 && stack2.Count > 0) || (stack1.Count > 0 && stack2.Count > 0 && stack1.Peek().val >= stack2.Peek().val))
{
root2 = stack2.Pop();
result.Add(root2.val);
root2 = root2.right;
}
}
return result;
}
}
}