[leetcode] 106. Construct Binary Tree from Inorder and Postorder Traversal

[leetcode] 106. Construct Binary Tree from Inorder and Postorder Traversal

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

分析

题目的意思是：用后序遍历和中序遍历，重构二叉树。

需要用到递归，后序遍历是左右中，中序遍历左中右。后序遍历可以得出根结点，中序遍历可以根据根结点位置，确定左右分支，然后继续递归解析。这里需要注意这种题目的解法非常固定，所以有意识的记下来是很有必要的。

代码

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: TreeNode* buildTree(vector& inorder, vector& postorder) { return build(inorder,postorder,0,inorder.size()-1,0,postorder.size()-1); } TreeNode* build(vector& inorder, vector& postorder,int in_start,int in_end,int po_start,int po_end){ if(in_start>in_end){ return NULL; } TreeNode* root=new TreeNode(postorder[po_end]); int i=0; for(i=in_start;ileft=build(inorder,postorder,in_start,i-1,po_start,po_start+len-1); root->right=build(inorder,postorder,i+1,in_end,po_start+len,po_end-1); return root; }};

参考文献

​​[编程题]construct-binary-tree-from-inorder-and-postorder-traversal​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。