首页 > 代码库 > Construct Binary Tree from Inorder and Postorder Traversal ——通过中序、后序遍历得到二叉树

Construct Binary Tree from Inorder and Postorder Traversal ——通过中序、后序遍历得到二叉树

2024-10-07 21:35:39   216人阅读

题意：根据二叉树的中序遍历和后序遍历恢复二叉树。

解题思路：看到树首先想到要用递归来解题。以这道题为例：如果一颗二叉树为{1,2,3,4,5,6,7}，则中序遍历为{4,2,5,1,6,3,7}，后序遍历为{4,5,2,6,7,3,1}，我们可以反推回去。由于后序遍历的最后一个节点就是树的根。也就是root=1，然后我们在中序遍历中搜索1，可以看到中序遍历的第四个数是1，也就是root。根据中序遍历的定义，1左边的数{4,2,5}就是左子树的中序遍历，1右边的数{6,3,7}就是右子树的中序遍历。而对于后序遍历来讲，一定是先后序遍历完左子树，再后序遍历完右子树，最后遍历根。于是可以推出：{4,5,2}就是左子树的后序遍历，{6,3,7}就是右子树的后序遍历。而我们已经知道{4,2,5}就是左子树的中序遍历，{6,3,7}就是右子树的中序遍历。再进行递归就可以解决问题了。

 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 *buildTree(vector<int> &inorder, vector<int> &postorder) {
13         if(inorder.size()!=postorder.size()||inorder.size()<1)
14             return NULL;
15         return build(inorder,postorder,0,inorder.size()-1,0,postorder.size()-1);
16     }
17     TreeNode *build(vector<int> &inorder, vector<int> &postorder, int startin,int endin,int startpost,int endpost){
18         if(startin>endin||startpost>endpost) return NULL;
19         if(startin==endin) return new TreeNode(inorder[startin]);
20         TreeNode *res = new TreeNode(postorder[endpost]);
21         int tmp=postorder[endpost];
22         int index=0;
23         while((startin+index)<=endin){
24             if(inorder[startin+index]==tmp)
25                 break;
26             index++;
27         }
28         res->left=build(inorder,postorder,startin,startin+index-1,startpost,startpost+index-1);
29         res->right=build(inorder,postorder,startin+index+1,endin,startpost+index,endpost-1);
30         return res;
31     }
32 };

 

Construct Binary Tree from Inorder and Postorder Traversal ——通过中序、后序遍历得到二叉树


联系
我们