LeetCode: Construct Binary Tree from Inorder and Postorder Traversal

第一次只用4个系数写dfs怎么写都不对，后来看了网上的答案发现写右子树的时候开始点不一样的。。。所以要用5个系数

 1 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     TreeNode* dfs(vector<int> &inorder, vector<int> &postorder, int inbeg, int postbeg, int len) {
13         if (!len) return NULL;
14         TreeNode *tmp = new TreeNode(postorder[postbeg+len-1]);
15         int leftlen, rightlen;
16         for (int i = inbeg; i < inbeg+len; i++) {
17             if (tmp->val == inorder[i]) {
18                 leftlen = i-inbeg;
19                 rightlen = len - leftlen -1;
20             }
21         }
22         tmp->left = dfs(inorder, postorder, inbeg, postbeg, leftlen);
23         tmp->right = dfs(inorder, postorder, inbeg+leftlen+1, postbeg+leftlen, rightlen);
24         return tmp;
25     }
26     TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
27         // Start typing your C/C++ solution below
28         // DO NOT write int main() function
29         if (inorder.size() != postorder.size() || inorder.size() == 0) return NULL;
30         int len = inorder.size();
31         return dfs(inorder, postorder, 0, 0, len);
32     }
33 };

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public int val;
 5  *     public TreeNode left;
 6  *     public TreeNode right;
 7  *     public TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public TreeNode BuildTree(int[] inorder, int[] postorder) {
12         if (inorder.Length != postorder.Length || inorder.Length == 0) return null;
13         int len = inorder.Length;
14         return dfs(inorder, postorder, 0, 0, ref len);
15     }
16     TreeNode dfs(int[] inorder, int[] postorder, int inbeg, int postbeg, ref int len)
17     {
18         if (len == 0) return null;
19         TreeNode tmp = new TreeNode(postorder[postbeg+len-1]);
20         int leftlen = 0;
21         int rightlen = 0;
22         for (int i = inbeg; i < inbeg+len; i++)
23         {
24             if (tmp.val == inorder[i])
25             {
26                 leftlen = i - inbeg;
27                 rightlen = len - leftlen - 1;
28             }
29         }
30         tmp.left = dfs(inorder, postorder, inbeg, postbeg, ref leftlen);
31         tmp.right = dfs(inorder, postorder, inbeg+leftlen+1, postbeg+leftlen, ref rightlen);
32         return tmp;
33     }
34 }

View Code