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

来自学习总结

1.问题描述:

根据一棵树的中序遍历与后序遍历构造二叉树(假设树中没有重复的元素)

中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3] 返回如下的二叉树：

2.思路

以后序数组的最后一个元素为切割点,先切中序数组,根据中序数组,反过来切后序数组,一层一层切下去,每次后续数组最后一个元素就是节点元素

一层一层切割的步骤:(递归)

1. 如果数组大小为0,说明是空节点
2. 若不为空,name去后序数组最后一个元素作为节点元素
3. 找到后序数组最后一个元素在中序数组的位置,作为切割点
4. 切割中序数组,切成中序左数组和中序右数组
5. 切割后续数组,切成后续数组和后序数组
6. 递归处理左区间和右区间

4.代码实现

public  TreeNode* traversal(vector<int>&  inorder,vector<int>& postorder){
    //1.
    if(postorder.size()==0)  return null;
    //2.后续遍历的最后一个元素,就是当前的节点
    int rootVal=postorder[postorder.size()-1];
    TreeNode* root=new TreeNode(rootVal);
    //叶子结点
    if(postorder.size()==1) return root;
    //3.切割点
    int delimiterIndex;
    for(delimiterIndex=0;delimiterIndex<inorder.size();delimiterIndex++){
        if(inorder[delimiterIndex]==rootVal) break;
    }
    //4切割中序数组
    //左闭右开区间[0,delimiterIndex)
    vector<int> leftInorder(inorder.begin(),inorder.begin()+delimiterIndex);
    //[delimiterIndex+1,end)
    vector<int> rightInorder(inorder.begin()+delimiterIndex+1,index.end());
    //舍弃末尾元素
    postorder.resize(postorder.size()-1);
    //5切割后序数组
    //左闭右开,注意这里使用了左中序数组大小作为切割点[0,leftorder.size)
    vector<int> leftPostOrder(postorder.begin(),postorder.begin()+leftInorder.size());
    //[leftInorder.size(),end)
    vector<int>  rightPostorder(postorder.begin()+leftInorder.size(),postorder.end());
    
    //6.
    root->left=traversal();
    root->right=traversal();
    return root;
}
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