分类 码不停题 下的文章

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


问题
  根据一棵树的中序遍历与后序遍历构造二叉树。可以假设数中没有重复元素。
  例如,给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

  返回以下的二叉树

分析
  首先明确两点:
  1. 后序遍历输出的数组,最后一个元素为树根。
  2. 中序遍历输出的数组,树根左边的元素构成左子树,树根右边的元素构成右子树。
  基于这两点,可以先从后序遍历中找到整个树的树根,再在中序遍历的结果中找到该树根,树根左边的元素即为左子树,右边的元素即为右子树。至此,该问题形成一个递归问题--左子树和右子树在后序遍历中也分别对应一个数组集合,对左子树和右子树分别递归即可还原原来的二叉树。

代码

/**
* 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<int>& inorder, vector<int>& postorder) {
    if(inorder.size()!=postorder.size())
      return NULL;
    if(inorder.size()==0 || postorder.size()==0)
      return NULL;

    int length=inorder.size();
    TreeNode* root=new TreeNode(postorder[length-1]);
    int root_inorder_index=-1;
    vector inorder_l,inorder_r,postorder_l,postorder_r;
    for(int i=0;i<length;i++)
      if(inorder[i]==postorder[length-1]){
        root_inorder_index=i;
        break;
      }

    for(int i=0;i<root_inorder_index;i++){
      inorder_l.push_back(inorder[i]);
      postorder_l.push_back(postorder[i]);
    }

    for(int i=root_inorder_index+1;i<inorder.size();i++){ 
      inorder_r.push_back(inorder[i]); 
      postorder_r.push_back(postorder[i-1]); 
    } 

    root->left=buildTree(inorder_l,postorder_l);
    root->right=buildTree(inorder_r,postorder_r);
    return root;
  }
};