-
Notifications
You must be signed in to change notification settings - Fork 1
/
106ConstructBTreeFromInOrderPostOrderTraversal_B.cs
169 lines (143 loc) · 4.98 KB
/
106ConstructBTreeFromInOrderPostOrderTraversal_B.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
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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace _106ConstructBTreeFromInOrderPostOrderTraversal_B
{
public class TreeNode
{
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int v)
{
val = v;
}
}
public class Range
{
public int start;
public int end;
public int getLength()
{
return end - start + 1;
}
public Range(int s, int e)
{
start = s;
end = e;
}
}
/*
* Leetcode:
* 106 Construct Binary Tree from Inorder and Post order traversal
*
* code reference:
* http://siddontang.gitbooks.io/leetcode-solution/content/tree/construct_binary_tree.html
*
* julia's C# implementation:
* https://github.com/jianminchen/Leetcode_C-/blob/master/106ConstructuBTreeFromInorderPostOrderTraversal.cs
*/
class Program
{
static void Main(string[] args)
{
}
static Hashtable htable = new Hashtable();
public static TreeNode buildTree(int[] inorder, int[] postorder)
{
int p_l = postorder.Length;
if (p_l == 0)
{
return null;
}
int i_l = inorder.Length;
for (int i = 0; i < i_l; i++)
{
htable[inorder[i]] = i;
}
return build(inorder, new Range(0, i_l - 1),
postorder, new Range(0, p_l - 1));
}
/*
*
1
--------|-------
2 3
----|---- ----|----
4 5 6 7
preorder traversal: 1245367
inorder traversal: 4251637
postorder traversal: 4526731
*
* code reference:
* http://siddontang.gitbooks.io/leetcode-solution/content/tree/construct_binary_tree.html
*
* Julia's comment:
practice the partition methods
*
* 2. online judge:
* 202 / 202 test cases passed.
Status: Accepted
Runtime: 192 ms
*/
public static TreeNode build(int[] inorder, Range iR,
int[] postorder, Range pR)
{
if (iR.start > iR.end || pR.start > pR.end)
{
return null;
}
int lastOne = pR.end;
TreeNode root = new TreeNode(postorder[lastOne]);
int v = postorder[lastOne]; // v - root value
int p = (int)htable[v]; // p - root position in inorder traversal array
int len = p - iR.start; // count - the size of left subtree, how many nodes
ArrayList l1 = partitionByMidPoint(iR, p);
ArrayList l2 = partitionByLength(pR, len);
root.left = build(inorder, (Range)l1[0], postorder, (Range)l2[0]);
root.right = build(inorder, (Range)l1[1], postorder, (Range)l2[1]);
return root;
}
/*
* 09/12/2015
* partition the interval to two, one is left side of mid position, another is right side
* assume r.start <= mid <= r.end
*
* this partition applies the inorder traversal array
* 09/13/2015
* After all the code is done, and then, thought about, add this additional note to help myself training better,
* for next time to review my code.
*
* inorder traversal array: Left subtree, Root Node, Right subtree
* so, if the root node position can be identified, then two subtree can be seperated by root node.
*/
public static ArrayList partitionByMidPoint(Range r, int mid)
{
ArrayList l = new ArrayList();
l.Add(new Range(r.start, mid - 1));
l.Add(new Range(mid + 1, r.end));
return l;
}
/* 09/12/2015
* partition the interval to two, first interval length is input argument: len,
* second one is the rest part, extra last one
*
* this partition is customized for post order traversal array.
* 09/13/2015
* add one more note to help:
* Post order traversal array: Left subtree, right subtree, Root node
* so partition them to add left subtree, right subtree to the list,
* only if the length of left subtree is known, then, partition can be done.
*/
public static ArrayList partitionByLength(Range r, int len)
{
ArrayList l = new ArrayList();
l.Add(new Range(r.start, r.start + len - 1));
l.Add(new Range(r.start + len, r.end - 1));
return l;
}
}
}