[LeetCode] Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

思路：

和Construct Binary Tree from Preorder and Inorder Traversal雷同，关键在于在inorder中找root，从而得以分割left/right subtree，并通过递归来重构。区别仅仅在于对postorder来说root为序列最后一个节点，以及left/right subtree左右边界index的计算稍有不同。

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

class Solution { public: TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) { if(inorder.size()!=postorder.size()) return NULL; int n = inorder.size(); return buildBT(inorder, postorder, 0, n-1, 0, n-1); } TreeNode *buildBT(vector<int> &inorder, vector<int> &postorder, int s1, int e1, int s2, int e2) { if(s1>e1 || s2>e2) return NULL; TreeNode *root = new TreeNode(postorder[e2]); int rootIndex = -1; for(int i=s1; i<=e1; i++) { if(inorder[i]==root->val) { rootIndex = i; break; } } if(rootIndex==-1) return NULL; int leftTreeSize = rootIndex - s1; int rightTreeSize = e1 - rootIndex; root->left = buildBT(inorder, postorder, s1, rootIndex-1, s2, s2+leftTreeSize-1); root->right = buildBT(inorder, postorder, rootIndex+1, e1, e2-rightTreeSize, e2-1); return root; } };

[LeetCode] Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

1. 递归解法：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

class Solution { public: vector<int> postorderTraversal(TreeNode *root) { vector<int> allNodeValues; postorderTrav(root, allNodeValues); return allNodeValues; } void postorderTrav(TreeNode *root, vector<int> &allNodeValues) { if(!root) return; postorderTrav(root->left, allNodeValues); postorderTrav(root->right, allNodeValues); allNodeValues.push_back(root->val); } };

2. 迭代解法：