ConstructBinaryTreeFromPreorderAndInorderTraversal [source code]
public class ConstructBinaryTreeFromPreorderAndInorderTraversal {
static
/******************************************************************************/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length != inorder.length)
return null;
Map<Integer, Integer> preorder_idx = new HashMap<> (), inorder_idx = new HashMap<> ();
for (int i = 0; i < preorder.length; i++) {
preorder_idx.put (preorder[i], i);
inorder_idx.put (inorder[i], i);
}
TreeNode root = new TreeNode (preorder[0]);
for (int i = 0; i < preorder.length; i++) {
insert (root, new TreeNode (preorder[i]), null, false, preorder_idx, inorder_idx);
}
return root;
}
void insert (TreeNode root, TreeNode node, TreeNode parent, boolean left_child, Map<Integer, Integer> preorder_idx, Map<Integer, Integer> inorder_idx) {
if (root == null) {
if (left_child)
parent.left = node;
else
parent.right = node;
return;
}
if (root.val == node.val)
return;
boolean inorder_before = inorder_idx.get (node.val) < inorder_idx.get (root.val);
int node_preorder_idx = preorder_idx.get (node.val), root_preorder_idx = preorder_idx.get (root.val);
if (node_preorder_idx > root_preorder_idx) {
insert (inorder_before ? root.left : root.right, node, root, inorder_before, preorder_idx, inorder_idx);
} else {
if (left_child)
parent.left = node;
else
parent.right = node;
if (inorder_before)
node.right = root;
else
node.left = root;
}
}
}
/******************************************************************************/
public static void main(String[] args) {
ConstructBinaryTreeFromPreorderAndInorderTraversal.Solution tester = new ConstructBinaryTreeFromPreorderAndInorderTraversal.Solution();
int[][] inputs = {
{3,9,20,15,7}, {9,3,15,20,7},
};
for (int i = 0; i < inputs.length / 2; i++) {
int[] preorder = inputs[2 * i], inorder = inputs[2 * i + 1];
tester.buildTree (preorder, inorder);
}
}
}
好像有点难, 暂时没有思路; 主要是build tree的算法, 好像并没有真正做过;
- 一个思路, 可能就是类似UF的思路: 从小的开始build起来, 然后一点一点的组合; 这个思路感觉这里不是非常的合适? 只是给了你一个traversal, 一点size相关的信息都没有;
- 另外一个思路, 就是直接一点一点insert的思路, 这个暂时还没有把握;
一个小的性质, PreOrder的第一个, 肯定是大root, 是不是? 这个是启发你用什么思路?
好像就是从root开始一个一个的插入, 大概有点思路; 不过不知道具体落实到代码难不难;
最后虽然是做出来了, 但是速度是221ms (0%), 可以说是非常差了, 关键是跟大部队差特别多, 几乎是在最右边了; 不知道到底哪里做错了; 这个就是一个O(N)的解法啊? 不对, 不是O(N), 是O(HN) = O(N^2).
没有editorial;
Hi guys, this is my Java solution. I read this post, which is very helpful.
The basic idea is here:
Say we have 2 arrays, PRE and IN.
Preorder traversing implies that PRE[0] is the root node.
Then we can find this PRE[0] in IN, say it’s IN[5].
Now we know that IN[5] is root, so we know that IN[0] - IN[4] is on the left side, IN[6] to the end is on the right side.
Recursively doing this on subarrays, we can build a tree out of it :)Hope this helps.
看完这个解释, 看来真的是一个divide&conquer的解法, 原来是可以做到的; 另外, divide&conquer可以理解为对应的就是一个returned recursion类似的思路;
public TreeNode buildTree(int[] preorder, int[] inorder) {
return helper(0, 0, inorder.length - 1, preorder, inorder);
}
public TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
if (preStart > preorder.length - 1 || inStart > inEnd) {
return null;
}
TreeNode root = new TreeNode(preorder[preStart]);
int inIndex = 0; // Index of current root in inorder
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == root.val) {
inIndex = i;
}
}
root.left = helper(preStart + 1, inStart, inIndex - 1, preorder, inorder);
root.right = helper(preStart + inIndex - inStart + 1, inIndex + 1, inEnd, preorder, inorder);
return root;
}
刚开始还真的是没有看懂, 看懂了之后, 只能说这个题目出的是真的不错, 非常准确的考察了traversal的性质:
这个题目, 一个关键点就是对于一个subtree, 他的PreOrder的traversal的第一个就是root, 找到这个root, 我们在InOrder里面定位inIndex, 那么InOrder里面, 0..inIndex-1的就全都是属于root.left subtree的nodes, inIndex+1..end的全是右边的child subtree, InOrder这一部分的divide是比较简单的; 稍微难处理一点的是PreOrder的拆分; 这个要借助于我们从InOrder的divide里面知道了两半的size, 然后在PreOrder里面, 我们知道, root后面肯定就是两个subtree的所有node总和, 但是我们不知道怎么拆分; 但是InOrder最后就告诉了我们; 这个图应该是解释的比较清楚的;
理解了之后只能说这个才是当之无愧的最优解; 不过能够自己想出来一个insert的解法, 其实我自己倒是觉得不丢人了;
当然, 他虽然思路清晰, 但是算法设计本身其实还是有很多可以优化的地方:
Nice solution! One improvement: remember to use HashMap to cache the inorder[] position. This can reduce your solution from 20ms to 5ms.
Here is the my Java solution:
public TreeNode buildTree(int[] preorder, int[] inorder) {
Map<Integer, Integer> inMap = new HashMap<Integer, Integer>();
for(int i = 0; i < inorder.length; i++) {
inMap.put(inorder[i], i);
}
TreeNode root = buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, inMap);
return root;
}
public TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, Map<Integer, Integer> inMap) {
if(preStart > preEnd || inStart > inEnd) return null;
TreeNode root = new TreeNode(preorder[preStart]);
int inRoot = inMap.get(root.val);
int numsLeft = inRoot - inStart;
root.left = buildTree(preorder, preStart + 1, preStart + numsLeft, inorder, inStart, inRoot - 1, inMap);
root.right = buildTree(preorder, preStart + numsLeft + 1, preEnd, inorder, inRoot + 1, inEnd, inMap);
return root;
}
这个是我自己已经想到的一个问题: 反向查询index这个方法; 这个题目还是用divide&conquer或者说returned recursion的思路更加聪明;
@longmanzz To determine preStart for the right sub-tree, we have to move towards the right of the preOrder array by a certain ‘offset’ value. This means we are skipping the next ‘offset’ number of indexes in the preOrder array to find the root of the right sub-tree.
This offset is determined by finding the size of the left sub-tree which is equal to the no. of indexes to the left of root found the inOrder array. Just think of (inIndex - inStart) as this offset. In other words, offset = ( inIndex - inStart ) .
Therefore the preStart for the right sub-tree is = preStart + offset + 1
It will be simpler if you draw the problem on a paper and iterate for this example:
Inorder sequence: D B E A F C
Preorder sequence: A B D E C F
另外, 就算是直接线性搜索, 他也应该加一个break; 下面有人实现, 加了break之后的速度几乎追上了用Map做反向查询的速度;
According to the article(see link below), the time is dependent on the search index of in-order sequence for each node. the average case running time is NlogN (when the tree is balanced), worst case is N^2(when the tree is skewed to left or right).
Article link: http://articles.leetcode.com/2011/04/construct-binary-tree-from-inorder-and-preorder-postorder-traversal.html
上面提到的那篇article里面, 摘抄一点东西:
Hint:
A good way to attempt this question is to work backwards. Approach this question by drawing a binary tree, then list down its preorder and inorder traversal. As most binary tree problems, you want to solve this recursively.
这个还真是, 上个星期一个BST问题也是, 单纯的mutation recursion做起来要人命, 但是returned recursion就非常的直白;
另外关于自己画tree找思路, 我当时写的时候, 找思路其实是找两个tree, 虽然比如PreOrder是一样的, 但是InOrder不一样, 然后看看能够从这个差别当中提取出什么信息: tree结构的差别是怎样反映在traversal的差别里的;
Solution:
Let us look at this example tree.
_______7______
/ \
__10__ ___2
/ \ /
4 3 _8
\ /
1 11
The preorder and inorder traversals for the binary tree above is:
preorder = {7,10,4,3,1,2,8,11}
inorder = {4,10,3,1,7,11,8,2}
The crucial observation to this problem is the tree’s root always coincides with the first element in preorder traversal. This must be true because in preorder traversal you always traverse the root node before its children. The root node’s value appear to be 7 from the binary tree above.
We easily find that 7 appears as the 4th index in the inorder sequence. (Notice that earlier we assumed that duplicates are not allowed in the tree, so there would be no ambiguity). For inorder traversal, we visit the left subtree first, then root node, and followed by the right subtree. Therefore, all elements left of 7 must be in the left subtree and all elements to the right must be in the right subtree.
We see a clear recursive pattern from the above observation. After creating the root node (7), we construct its left and right subtree from inorder traversal of {4, 10, 3, 1} and {11, 8, 2} respectively. We also need its corresponding preorder traversal which could be found in a similar fashion. If you remember, preorder traversal follows the sequence of root node, left subtree and followed by right subtree. Therefore, the left and right subtree’s postorder traversal must be {10, 4, 3, 1} and {2, 8, 11} respectively. Since the left and right subtree are binary trees in their own right, we can solve recursively!
We left out some details on how we search the root value’s index in the inorder sequence. How about a simple linear search? If we assume that the constructed binary tree is always balanced, then we can guarantee the run time complexity to be O(N log N), where N is the number of nodes. However, this is not necessarily the case and the constructed binary tree can be skewed to the left/right, which has the worst complexity of O(N^2).
A more efficient way is to eliminate the search by using an efficient look-up mechanism such as hash table. By hashing an element’s value to its corresponding index in the inorder sequence, we can do look-ups in constant time. Now, we need only O(N) time to construct the tree, which theoretically is the most efficient way.
For illustration purpose, the below code uses a simple array for table look-up, which is restricted to elements of 0 to 255 only. You should be able to extend it easily to use a hash table.
const int MAX = 256;
// a fast lookup for inorder's element -> index
// binary tree's element must be in the range of [0, MAX-1]
int mapIndex[MAX];
void mapToIndices(int inorder[], int n) {
for (int i = 0; i < n; i++) {
assert(0 <= inorder[i] && inorder[i] <= MAX-1);
mapIndex[inorder[i]] = i;
}
}
// precondition: mapToIndices must be called before entry
Node *buildInorderPreorder(int in[], int pre[], int n, int offset) {
assert(n >= 0);
if (n == 0) return NULL;
int rootVal = pre[0];
int i = mapIndex[rootVal]-offset; // the divider's index
Node *root = new Node(rootVal);
root->left = buildInorderPreorder(in, pre+1, i, offset);
root->right = buildInorderPreorder(in+i+1, pre+i+1, n-i-1, offset+i+1);
return root;
}
合理的lookup之后复杂度是O(N), 这个应该不难想到;
I din’t find iterative solutions discussed in the old Discuss. So, I thought, I will add my solution in here.
The idea is as follows:
- Keep pushing the nodes from the preorder into a stack (and keep making the tree by adding nodes to the left of the previous node) until the top of the stack matches the inorder.
- At this point, pop the top of the stack until the top does not equal inorder (keep a flag to note that you have made a pop).
- Repeat 1 and 2 until preorder is empty. The key point is that whenever the flag is set, insert a node to the right and reset the flag.
class Solution {
public:
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
if(preorder.size()==0)
return NULL;
stack<int> s;
stack<TreeNode *> st;
TreeNode *t,*r,*root;
int i,j,f;
f=i=j=0;
s.push(preorder[i]);
root = new TreeNode(preorder[i]);
st.push(root);
t = root;
i++;
while(i<preorder.size())
{
if(!st.empty() && st.top()->val==inorder[j])
{
t = st.top();
st.pop();
s.pop();
f = 1;
j++;
}
else
{
if(f==0)
{
s.push(preorder[i]);
t -> left = new TreeNode(preorder[i]);
t = t -> left;
st.push(t);
i++;
}
else
{
f = 0;
s.push(preorder[i]);
t -> right = new TreeNode(preorder[i]);
t = t -> right;
st.push(t);
i++;
}
}
}
return root;
}
};
看的有点头疼, 先从底下翻了一个简洁的java版本看一下:
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length == 0) return null;
Stack<TreeNode> s = new Stack<>();
TreeNode root = new TreeNode(preorder[0]), cur = root;
for (int i = 1, j = 0; i < preorder.length; i++) {
if (cur.val != inorder[j]) {
s.push(cur);
cur = cur.left = new TreeNode(preorder[i]);
} else {
j++;
while (!s.empty() && s.peek().val == inorder[j]) {
cur = s.pop();
j++;
}
cur = cur.right = new TreeNode(preorder[i]);
}
}
return root;
}
}
非常的难理解, 画了一个trace:
虚实结合的盯了很久, 还是看不懂; 感觉这个例子还是不够general; 自己重新再找一个例子;
想了很久实际上还是不是很理解这个算法, 这个算法绝对算得上是我刷题到现在为止最难的算法之一了;
算法本身的结构还是大概有点印象的, 基本就是类似普通的iterative DFS一样的, 用push left beam的思路, 然后寻找下潜点; 一个重要的性质是, [j]是第一个个尚未被insert的node; 所以整个算法其实就是先寻找insert[j]的位置, 也就是最左下的方向: 这个就是循环的第一个branch做的工作, 不停的push left; 当到了一个点, 找到了, 比如insert 1的位置的时候, 放上去, 然后这个时候Stack里面全是1的parent, 这些也全都是已经被insert了的(在PreOrder里面已经被走过), 我们要在InOrder里面也跳过他们, 这个就是这个while循环的作用; 这个while循环是一个顺着左边大梁往上回头的过程, 当走到一个位置停止的时候, 说明又碰到了一个uninserted [j], 这个时候把[i]给扔到当前的cur的右边child; 事实上, 这一个insert right child的过程是最难理解的; 比如看上面黄色c2的位置, 你怎么知道这个时候就可以安心的把[i] = 3给insert到cur.right呢?
这个时候, 0..i-1范围内的数字(4,2,1), 一个在Stack里面, 一个在0..j-1; 关键就是理解, 当这个while循环停止的时候, 实际上是在左边大梁上面的一个点上面, 这个时候我们手上有什么性质?
当我们while循环被这个cur挡住的时候, 实际上是被[j]挡住的; 这个时候说明[j]是一个un inserted的数字; 而我们停在cur, 说明[j]是在cur的right subtree里面; 那么我们下一步, 应该是一个类似下潜的操作: 找到cur.right, 也就是right subtree的root; 然而这个数字正好就是这个时候的[i]:
为什么[j]一定在cur的right subtree? 假如cur.right存在, 那么这个是很自然的, 因为[j]是InOrder里面的, un inserted, 那么下一个insert位置肯定是在cur的右边subtree;
这里这个2也就是cur的left subtree, 也就是A, 肯定是已经处理完了的; 因为A是最小的一部分数字, 这个算法把这部分最小的数字处理完了之后, 开始跳子; A本身里面的left beam肯定都被跳掉了; 那么要停在2这里?
这个图应该是比较实在的了, 但是我还是想追问一个问题, 到底怎么知道[j]一定在cur的right subtree里面? 那么, 假设3不在2的right subtree里面; 那么3在哪儿呢? 只能在4的right subtree, 因为A已经处理完了; 那么2到底有没有right subtree? 假设有, 那么也就是说B是存在的, 那么[j]肯定还是在B里, 只不过是另外一个数字而已; 假设2没有subtree; 类似这里的3.5, 一定在while里面被跳掉:
不过你怎么证明这个一定会被跳掉?
大概有点思路:
可以看到, 假如是3.5这样一个没有right child的node, 他在InOrder里面一定是紧紧的跟着A里面的最大值(这个时候cur肯定在A的最大值, 因为算法设计的方式就是这样, 每一个subtree最后一步都是add right child, 最后彻底退出一个subtree的时候, 肯定是刚add完它的最大值); 要证明3.5会被跳掉, 实际上就是证明InOrder里面, 当前的cur=3的下一位一定是3.5, 因为j就是一点一点+1向前移动的; 比如把3给insert了之后, 下一步cur就是3了, 然后这个iteration(right child adding branch)就结束了, 然后下一个iteration开始的时候, [i]=6, cur=3, [j] = 3;
算了, 用纯粹imperative的方法简直是无法理解; 反正你看着上面这个图上面Stack的画法;
算了, 真的是搞不懂;
Similar idea. A simpler version.
class Solution {
public:
TreeNode *buildTree(vector<int> &pre, vector<int> &in) {
int i=0,j=0;
TreeNode *root=new TreeNode(0x80000000);
TreeNode *pp=NULL,*ptr=root;
stack<TreeNode*> sn;sn.push(root);
while (j<in.size()) {
if (sn.top()->val==in[j]) {
pp=sn.top();
sn.pop();
j++;
} else if (pp) {
ptr=new TreeNode(pre[i]);
pp->right=ptr;pp=NULL;
sn.push(ptr);
i++;
} else {
ptr=new TreeNode(pre[i]);
sn.top()->left=ptr;
sn.push(ptr);
i++;
}
}
ptr=root->left;delete root;
return ptr;
}
};
大概画了一下, 思路应该是类似的, 但是因为是用的conditional increment的设计方式, 最后代码反而更加难懂了;
Similiar idea in cpp.
ppre and pin are pointers to current item.
Unlike post and in case, we need to construct tree from head to the tail of these two orders.
class Solution {
public:
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
if (preorder.size() == 0) return NULL;
int ppre = 0, pin = 0;
TreeNode *root = new TreeNode(preorder.at(ppre++));
TreeNode *p = NULL;
stack<TreeNode *> roots;
roots.push(root);
while (true) {
if (inorder.at(pin) == roots.top()->val) {
p = roots.top();
roots.pop();
pin++;
if (pin == inorder.size()) break;
if (roots.size() && inorder.at(pin) == roots.top()->val) continue;
p->right = new TreeNode(preorder.at(ppre));
ppre++;
roots.push(p->right);
}
else {
p = new TreeNode(preorder.at(ppre));
ppre++;
roots.top()->left = p;
roots.push(p);
}
}
return root;
}
};
先摆着, 是真的没时间看了;
My accepted solution.
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
TreeNode* root = NULL;
int size = preorder.size();
if(size <= 0) return root;
root = new TreeNode(preorder[0]);
if(size == 1) return root;
stack<TreeNode*> s;
s.push(root);
TreeNode* node;
int i=0, j=0;
while(i+1 < size) {
node = s.top();
if( node->val != inorder[j]) {
node->left = new TreeNode(preorder[++i]);
node = node->left;
s.push(node);
}
else {
s.pop();
j++;
if(s.empty() || inorder[j] != s.top()->val) {
node->right = new TreeNode(preorder[++i]);
node = node->right;
s.push(node);
}
}//if
}//while
return root;
}
@gpraveenkumar Here I provide my understanding on how the iterative solution work.
- Let’s first observe the sequence of inorder traversal.
####$—##$—0+++0: The root node of a tree#: the left child or grandchildren of root node 0, without right child$: the left child or grandchildren of root node 0, with a right child or subtree.—: represent right subtree of node $+++: represent right subtree of root node.- Let’s observe the sequence of preorder traveral
0$##$###------+++- The symbols are the same.
- Maintain two pointers: ptrin, ptrpre
- ptrpre: always points to the next node that is about to be created.
- ptrin: when we keep pushing into stack, ptrin always points to the deepest left child of a subtree. When we keeping popping out nodes, ptrin points to nodes that has no right child, until it points to the root of the right subtree of a node that is just popped out from the stack.
- Maintain a stack
- Similar with the stack in inorder traversal, it always stores the chain of left children in a subtree.
- When pushing stack, we are traversing the chain of left children in a subtree, and we keeping creating new node and make it as the left child of the node at stack top.
- When poping stack, we always pop out a node that has no right child, until we find a node that has right child (subtree).
- Maintain a temp pointer, that always points to a node popped from stack, the last node that is popped out from the stack has right child (subtree). So the newly created node will be the right child of temp.
- Procedures of my algorithm:
- Create the root node of the entire tree, record the root node for the purpose of return. Push the root node into the stack.
- While we has remaining node to create
a. When we enter a new iteration, ptrin always points to the deepest left grandchild of a tree. So as long as we have not reached it, we can safely keep creating new left child (grandchild) for top node at stack. This actually creating the chain of left children for a tree, namely ###$#$0. The newly-created node will be pushed in the stack. So, next created node will be its left child.
b. Now, after the previous step, we have reached the deepest left child of a tree. Remember inorder traveral, now we need to retreat from the deepest left child until we find the first node that has a right child or subtree. We use a temp pointer to record the node that has right child, than we create the right child for it. This is achievable, because ptrpre always points to the next node that will be created. In other word, now, the node pointed by ptrpre is the right child. This invariant is ensured by the characteristics of preorder traversal. Remember the symbol presentation: 0$##$###------+++. After we create the left children chain: 0$##$###, now the ptrpre points to the first -, which is the right child of the first node with right child (the second $).
c. Repeat step (a) and step (c) until we create all nodes.
他这里的解释跟我讲的是有点道理的, 但是有些我没有理解的东西他其实也没有解释清楚; 比如我上面的3.5为什么会被跳过, 这个是我最不能证明的地方; 至于我用AB来分析的那个跟这里是类似的, 3.5如果有right subtree, 反而不难理解;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if(preorder.empty()) return NULL;
int ppre = 0, pin = 0;
TreeNode* root = new TreeNode(preorder[ppre++]);
stack<TreeNode*> stk;
stk.push(root);
while(true) {
while(stk.top()->val != inorder[pin]) {
TreeNode* newnode = new TreeNode(preorder[ppre++]);
stk.top()->left = newnode;
stk.push(newnode);
}
TreeNode* node;
while(!stk.empty() && stk.top()->val == inorder[pin]) {
node = stk.top();
stk.pop();
pin++;
}
if(ppre == preorder.size()) break;
TreeNode* newnode = new TreeNode(preorder[ppre++]);
node->right = newnode;
stk.push(newnode);
}
return root;
}
后来想了一下, 好像大概知道怎么解释了; 比如还是那个[1 2 3] 3.5 4的例子:
当你把3insert之后, cur变成3, 然后进入下一个iteration, [i]变成6, [j]这个时候还是3, cur==[j], 进入branch2, j++, [j]变成3.5, 等于Stack top, 所以cur变成3.5, [j]继续前进到4, 这里就是为什么3.5因为没有right child所以就一定会被跳过: 假如3.5有right child, 那么在InOrder里面, 3.5和4之间肯定还有数字, 那么我们[j]就不可能从3.5直接前进到4, 也就不可能再一次满足[j]==Stack top;
所以我们证明了, while循环停止的这个cur, 肯定恨死有right subtree的, 而且让其停止的[j]就在right subtree里面, 然后[i]就是right subtree的root;
接下来整个算法基本就好理解了; 上面后面回复下面的很多类似的算法我都没有看了, 但是好像看得出来, 这题其实不是iterative DFS那里那样单纯是记忆的固定的套路, 而是确实是一个ad-hoc的算法, 就是人家很聪明, 都想出来用Stack这么做而已; 大部分的人的思路都是先按照PreOrder一直push left, 然后push到跟InOrder汇合的位置, 再开始跳子, 跳子停止的地方是插入[i]的地方; 等等;
关于Python里面subarray问题的实现方式的一个讨论:
The slice operation usually costs k space when you slice like list[:k], because you create a new list whose size is k. If you want to get rid of MLE, a normal way is using indexes, which means you can input the lower and upper bound indexes as parameters. For instance, the above example can call a helper function like: buildTreeHelper(preorder, inorder, lower1, upper1, lower2, upper2), lower1 and upper1, lower2 and upper2 are corresponding to the preorder and inorder indexes respectively.
submission最优解基本都是那个recursion divide&conquer的做法;
Problem Description
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
For example, given
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Return the following binary tree:
3
/ \
9 20
/ \
15 7
Difficulty:Medium
Total Accepted:129.2K
Total Submissions:386.3K
Contributor:LeetCode
Companies
bloomberg
Related Topics
arraytreedepth-first search
Similar Questions
Construct Binary Tree from Inorder and Postorder Traversal