ConstructBinaryTreeFromInorderAndPostorderTraversal [source code]
public class ConstructBinaryTreeFromInorderAndPostorderTraversal {
static
/******************************************************************************/
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (inorder.length != postorder.length || inorder.length == 0)
return null;
Map<Integer, Integer> inorder_indices = new HashMap<> ();
for (int i = 0; i < inorder.length; i++)
inorder_indices.put (inorder[i], i);
return build (inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1, inorder_indices);
}
TreeNode build (int[] inorder, int in_start, int in_end, int[] postorder, int post_start, int post_end, final Map<Integer, Integer> inorder_indices) {
if (in_start > in_end || post_start > post_end)
return null;
int root_num = postorder[post_end];
int root_inorder_index = inorder_indices.get (root_num);
TreeNode root = new TreeNode (root_num);
root.left = build (inorder, in_start, root_inorder_index - 1, postorder, post_start, post_start + root_inorder_index - 1 - in_start, inorder_indices);
root.right = build (inorder, root_inorder_index + 1, in_end, postorder, post_end - 1 + (root_inorder_index + 1 - in_end), post_end - 1, inorder_indices);
return root;
}
}
/******************************************************************************/
public static void main(String[] args) {
ConstructBinaryTreeFromInorderAndPostorderTraversal.Solution tester = new ConstructBinaryTreeFromInorderAndPostorderTraversal.Solution();
int[][] inputs = {
{2,1}, {2, 1},
};
int k = 2;
for (int i = 0; i < inputs.length / k; i++) {
int[] inorder = inputs[k * i], postorder = inputs[k * i + 1];
System.out.println (TreeNode.serialize (tester.buildTree (inorder, postorder)));
}
}
}
虽然很想装个逼用Stack做法来写, 但是还是少作点死, 这种大拿算法我现在真的是没有驾驭住; 老老实实用divide&conquer写; 就算你把Stack做法给写出来了, 真正面试的时候你敢用这个做法吗? 没有办法讲明白给面试官听的话, 反而是负分;
base case用leaf比用pre leaf(长度为1的时候直接返回一个node)要好处理一些, test1就是break了这个; 后面回头去看了一眼上一题的答案, 原来实际上这里的PostOrder只要维护一个参数就行了: 每一个段只要维护end_index就行了; 不过反正维护两头也没有什么大问题, 还好理解一些; 最后的速度是5ms (66%);
没有editorial;
The the basic idea is to take the last element in postorder array as the root, find the position of the root in the inorder array; then locate the range for left sub-tree and right sub-tree and do recursion. Use a HashMap to record the index of root in the inorder array.
public TreeNode buildTreePostIn(int[] inorder, int[] postorder) {
if (inorder == null || postorder == null || inorder.length != postorder.length)
return null;
HashMap<Integer, Integer> hm = new HashMap<Integer,Integer>();
for (int i=0;i<inorder.length;++i)
hm.put(inorder[i], i);
return buildTreePostIn(inorder, 0, inorder.length-1, postorder, 0,
postorder.length-1,hm);
}
private TreeNode buildTreePostIn(int[] inorder, int is, int ie, int[] postorder, int ps, int pe,
HashMap<Integer,Integer> hm){
if (ps>pe || is>ie) return null;
TreeNode root = new TreeNode(postorder[pe]);
int ri = hm.get(postorder[pe]);
TreeNode leftchild = buildTreePostIn(inorder, is, ri-1, postorder, ps, ps+ri-is-1, hm);
TreeNode rightchild = buildTreePostIn(inorder,ri+1, ie, postorder, ps+ri-is, pe-1, hm);
root.left = leftchild;
root.right = rightchild;
return root;
}
基本是一个意思, 核心就是用returned recursion的思路来写;
This is my version: similar idea, but no HashMap needed!
(TreeNode end is the boundary of left subtree.)
int pInorder; // index of inorder array
int pPostorder; // index of postorder array
private TreeNode buildTree(int[] inorder, int[] postorder, TreeNode end) {
if (pPostorder < 0) {
return null;
}
// create root node
TreeNode n = new TreeNode(postorder[pPostorder--]);
// if right node exist, create right subtree
if (inorder[pInorder] != n.val) {
n.right = buildTree(inorder, postorder, n);
}
pInorder--;
// if left node exist, create left subtree
if ((end == null) || (inorder[pInorder] != end.val)) {
n.left = buildTree(inorder, postorder, end);
}
return n;
}
public TreeNode buildTree(int[] inorder, int[] postorder) {
pInorder = inorder.length - 1;
pPostorder = postorder.length - 1;
return buildTree(inorder, postorder, null);
}
感觉typed trace更适合return recursion. 这种recursion用mutation recursion那种直接一个tree的好像不太好画, 因为parent还需要等下层的结果, 用tree trace好像不好表达;
这里他的两个全局index实际上就是一个可以变动的参数, 所以我用这两个参数来标记iteration; 同时, 图形上的trace不要跟上一题那样, 所有的iteration都留下来, 乌七八糟的其实也看不清楚; 用先写后擦的方法, 来记录当前有效的比如index就行了;
看这个trace的组织的方式, 图形上面, 就用两根红线代表index就行了; 然后trace本身:
- 同一个level的用一个缩进, 不同level的用不同的缩进; level内的内容记录关键的变量信息;
- 同一个level为了区分arguments/state before iteration和iteration内部的内容, 用一个框框标记出来state just before entry;
行了, trace也画完了, 那么他这个算法本身是什么讲究呢?
这个trace应该更好理解一些; 当然, 最好还是从root level decision的角度来理解; 你看他最上面这一层, 当把4 3扔给right subtree的时候, 返回来上来的时候已经变成了1 0了, 也就是说这个算法其实自动用相同的顺序来处理InOrder和PostOrder: 都是从右向左扫过相同的长度;
讲起来很简单, 但是实际上这个算法的逻辑设计并不简单, 你看他这里这个算法, 比较难的地方, 是怎么判断是否有right subtree和left subtree;
我们看17这里, 对应的是4 2 20的state;
通过举例子的方法可以看到为什么他判断是否存在right subtree的方法是合理的; 左边应该也是类似的一个思路; 总体来说, 这个算法的复杂程度就真的有点厉害; 因为不是跟传统的divide&conquer做法那样直接砍断InOrder, 所以最后是不需要Map的; 巧妙的逻辑可以让两个traversal里面的index以同level内同速的方式移动;
TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
return create(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1);
}
TreeNode* create(vector<int> &inorder, vector<int> &postorder, int is, int ie, int ps, int pe){
if(ps > pe){
return nullptr;
}
TreeNode* node = new TreeNode(postorder[pe]);
int pos;
for(int i = is; i <= ie; i++){
if(inorder[i] == node->val){
pos = i;
break;
}
}
node->left = create(inorder, postorder, is, pos - 1, ps, ps + pos - is - 1);
node->right = create(inorder, postorder, pos + 1, ie, pe - ie + pos, pe - 1);
return node;
}
跟我一样多用一个index的笨蛋;
class Solution {
public:
TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
if(inorder.size() == 0)return NULL;
TreeNode* p;
TreeNode* root;
vector<int> vint;
vector<TreeNode*> vtn;
root = new TreeNode(postorder.back());
vtn.push_back(root);
postorder.pop_back();
while(true)
{
if(inorder.back() == vtn.back()->val)
{
p = vtn.back();
vtn.pop_back();
inorder.pop_back();
if(inorder.size() == 0) break;
if(vtn.size())
if(inorder.back() == vtn.back()->val)continue;
p->left = new TreeNode(postorder.back());
postorder.pop_back();
vtn.push_back(p->left);
}
else
{
p = new TreeNode(postorder.back());
postorder.pop_back();
vtn.back()->right = p;
vtn.push_back(p);
}
}
return root;
}
};
该来的还是要来的; 还特么是两个Stack的做法;
有人尝试解释这个算法:
Below is the O(n) solution from @hongzhi but that discuss is closed now 'cause @hongzhi says little about his code.
https://oj.leetcode.com/discuss/6334/here-is-my-o-n-solution-is-it-neat
I’ve modified some of and tried this code and got AC.
Just share about some comprehension about his code.I’ve modified vtn(vector) to stn(stack) in that stack is probably what this algs means and needs.
What matters most is the meaning of stn.
Only nodes whoes left side hasn’t been handled will be pushed into stn.
跟朱神说的一样, 高手都是从分析invariant开始的;
And inorder is organized as (inorder of left) root (inorder of right),
And postorder is as (postorder of left) (postorder of right) root.
So at the very begin, we only have root in stn and we check if inorder.back() == root->val and in most cases it’s false(see Note 1). Then we make this node root’s right sub-node and push it into stn.
这个讲的不对, 这里insert给root.right的是PostOrder的最后一个, 不是InOrder的最后一个;
Note 1: this is actually (inorder of right).back() == (postorder of right).back(), so if only there’s no right subtree or the answer will always be false.
Note 2: we delete one node from postorder as we push one into stn.
Now we have [root, root’s right] as stn and we check inorder.back() == stn.top()->val again.
- true means inorder.back() is the root node and needs handled left case.
- false means inorder.back() is the next right sub-node
So when we encounter a true, we will cache stn.top() as p and delete both nodes from inorder and stn.
Then we check inorder.size(), if there’s no nodes left, it means p has no left node.
Else the next node in inorder could be p’s left node or p’s father which equals to the now stn.top() (remember we popped p from stn above).
If the latter happens, it means p has no left node and we need to move on to p’s father(stn.top()).
If the former happens, it means p has one left node and it’s postorder.back(), so we put it to p’s left and delete it from the postorder and push the left node into stn 'cause it should be the next check node as the postorder is organized as above.
That’s all of it. The algs just build a binary tree. :)
Inform me if there’s anything vague or wrong, I’m open to any suggestions.
class Solution {
public:
TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
if(inorder.size() == 0)return NULL;
TreeNode *p;
TreeNode *root;
stack<TreeNode *> stn;
root = new TreeNode(postorder.back());
stn.push(root);
postorder.pop_back();
while(true)
{
if(inorder.back() == stn.top()->val)
{
p = stn.top();
stn.pop();
inorder.pop_back();
if(inorder.size() == 0) break;
if(stn.size() && inorder.back() == stn.top()->val)
continue;
p->left = new TreeNode(postorder.back());
postorder.pop_back();
stn.push(p->left);
}
else
{
p = new TreeNode(postorder.back());
postorder.pop_back();
stn.top()->right = p;
stn.push(p);
}
}
return root;
}
};
感觉这个while true的循环好像还好理解一些; 而且也没有被iterative DFS那种算法支配的恐惧感了;
好像还是跟第一题那个算法差不多的, 主循环走的是PostOrder, 然后在没有和InOrder对其之前, 一直insert at right and push stack, 等到对齐的时候, 有一个类似跳子什么的操作, 最后的目的是把所有的InOrder都处理完, 这个是跟上一个算法很一致的;
简单画了一个trace, 感觉可以说是一模一样的算法; 就是写法上有差别; 还有他避免了直接的指针assignment, 类似cur = cur.left这种, 而是用push/pop来实现类似的操作, 这个在iterative DFS的时候其实也见到过了;
跟上一题一样, 这个算法虽然是用iteration写的, 不过理解的时候, 适当的掺杂一些类似root level decision这样的recursion的分析技巧, 有助于理解;
大概分析一下;
This is the process of inserting. Push the next posorder[-1] into stack and also attatch current stack top's right as long as we think stack.top has right subtree. Keep doing this until we met 17, which has no subtree. Then we have to skip as much as possible in stack at the same time with their elements in inorder. As much as possible means we can't skip a subroot like 20, because it has left subtree.
哎呀, 好像讲的也不清楚, 算了, 不去discuss现眼了;
We have to stop at 20 because we know it has left subtree. How? 也不知道怎么具体表述好了;
3和20 InOrder之间有东西, 说明15一定是20的left subtree里面的; 然后还是照样的, 在PostOrder里面找到这个left subtree的root; 这里正好还是15自己;
总体思路还是先根据PostOrder来insert & push, 到底之后, 反弹跳子, 找到断点就insert left, 寻找新的下潜机会;
java版本:
public class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (inorder == null || inorder.length < 1) return null;
int i = inorder.length - 1;
int p = i;
TreeNode node;
TreeNode root = new TreeNode(postorder[postorder.length - 1]);
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
p--;
while (true) {
if (inorder[i] == stack.peek().val) { // inorder[i] is on top of stack, pop stack to get its parent to get to left side
if (--i < 0) break;
node = stack.pop();
if (!stack.isEmpty() && inorder[i] == stack.peek().val) {// continue pop stack to get to left side
continue;
}
node.left = new TreeNode(postorder[p]);
stack.push(node.left);
} else { // inorder[i] is not on top of stack, postorder[p] must be right child
node = new TreeNode(postorder[p]);
stack.peek().right = node;
stack.push(node);
}
p--;
}
return root;
}
}
因为没有方便的pop_back操作, 所以就用一个index来完成;
反正这个人解释的其实还算一般吧. 感觉他还是没有理解这个算法的行为本身;
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (inorder.length == 0 || postorder.length == 0) return null;
int ip = inorder.length - 1;
int pp = postorder.length - 1;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode prev = null;
TreeNode root = new TreeNode(postorder[pp--]);
stack.push(root);
while (pp >= 0) {
while (!stack.isEmpty() && stack.peek().val == inorder[ip]) {
prev = stack.pop();
ip--;
}
TreeNode newNode = new TreeNode(postorder[pp]);
if (prev != null) {
prev.left = newNode;
} else if (!stack.isEmpty()) {
TreeNode currTop = stack.peek();
currTop.right = newNode;
}
stack.push(newNode);
prev = null;
pp--;
}
return root;
}
This is my iterative solution, think about “Constructing Binary Tree from inorder and preorder array”, the idea is quite similar. Instead of scanning the preorder array from beginning to end and using inorder array as a kind of mark, in this question, the key point is to scanning the postorder array from end to beginning and also use inorder array from end to beginning as a mark because the logic is more clear in this way.
The core idea is: Starting from the last element of the postorder and inorder array, we put elements from postorder array to a stack and each one is the right child of the last one until an element in postorder array is equal to the element on the inorder array. Then, we pop as many as elements we can from the stack and decrease the mark in inorder array until the peek() element is not equal to the mark value or the stack is empty. Then, the new element that we are gonna scan from postorder array is the left child of the last element we have popped out from the stack.
这哪里是什么idea, 这个就是把代码的逻辑给转述了一遍, 一点说明和理由都没有给;
但是他代码写的很好, 跟iterative DFS我见过的几个代码风格很像, 一个while循环里面, 每一个iteration上来又是一个小while; 不过那里的小while好像都是push大梁操作, 这里的反而是pop;
这个prev好像记录的就是the last root that has left subtree. 总体来说代码的结合还是挺不错的, 不过这个算法, 我建议还是重点理解逻辑;
public TreeNode buildTree(int[] inorder, int[] postorder) {
//boundary case
if(inorder.length == 0) return null;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode root = new TreeNode(postorder[postorder.length-1]);
stack.push(root);
int i = postorder.length-2, j = inorder.length-1;//i is index in postorder[], j is index in inorder[]
while(i >= 0){
TreeNode curr = stack.peek();
if(curr.val != inorder[j]){
//as long as we have not reach the rightmost node we can safely follow right path and attach right child
TreeNode right = new TreeNode(postorder[i]);
curr.right = right;
stack.push(right);
i--;
}else{
//found the node from stack where we have not visited its left subtree
while(!stack.isEmpty() && stack.peek().val == inorder[j]){
curr = stack.pop();
j--;
}
TreeNode left = new TreeNode(postorder[i]);
curr.left = left;
stack.push(left);
i--;
}
}
return root;
}
大概扫了一眼估计应该是差不多; 这个是一个跟之前第一题那个非常类似的版本了;
submission最优解: 2(93):
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
return buildTree(inorder, inorder.length-1, 0, postorder, postorder.length-1);
}
private TreeNode buildTree(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart) {
if (postStart < 0 || inStart < inEnd)
return null;
//The last element in postorder is the root.
TreeNode root = new TreeNode(postorder[postStart]);
//find the index of the root from inorder. Iterating from the end.
int rIndex = inStart;
for (int i = inStart; i >= inEnd; i--) {
if (inorder[i] == postorder[postStart]) {
rIndex = i;
break;
}
}
//build right and left subtrees. Again, scanning from the end to find the sections.
root.right = buildTree(inorder, inStart, rIndex + 1, postorder, postStart-1);
root.left = buildTree(inorder, rIndex - 1, inEnd, postorder, postStart - 1-(inStart - rIndex));
return root;
}
}
线性扫居然比HashMap反向lookup还要快, 你说奇怪不奇怪;
Problem Description
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
For example, given
inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]
Return the following binary tree:
3
/ \
9 20
/ \
15 7
Difficulty:Medium
Total Accepted:101.6K
Total Submissions:307.3K
Contributor:LeetCode
Companies
microsoft
Related Topics
arraytreedepth-first search
Similar Questions
Construct Binary Tree from Preorder and Inorder Traversal