Rabbet

悦已者

0%

从中序遍历与后序遍历序列构造二叉树

发表于 更新于 分类于
本文字数： 1.3k 阅读时长 ≈ 1 分钟

题目描述

  根据一棵树的中序遍历与后序遍历构造二叉树。

输入输出样例

中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3]

返回的二叉树如下：
1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

题解

  具体题解可以参考这里,这里我就把中序与后序的实现的区别图贴与代码实现贴出来，以供大家参考：

avatar

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
28
29
30
31
32
33
34
35
36
37
38
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return create(inorder,0,inorder.size()-1,
                      postorder,0,postorder.size()-1);
    }
	     TreeNode* create(vector<int>& inorder,int inStart,int inEnd,
    vector<int>& postorder,int posStart,int posEnd) {
        // 递归出口
        if (posStart > posEnd) return nullptr;
        int rootval = postorder[posEnd];
        int index = -1;
        for (int i = inStart; i <= inEnd; i++) {
            if (rootval == inorder[i]) {
                index = i;
                break;
            }
        } 
		int leftsize = index - inStart;
        TreeNode* root = new TreeNode(rootval);
        root->left = create(inorder,inStart,index-1,
                            postorder,posStart,posStart+leftsize-1);
        root->right = create(inorder,index+1,inEnd,
                            postorder,posStart+leftsize,posEnd-1);
        return root;
    }
};