【Construct Binary Tree from Inorder and Postorder Traversal】cpp-白红宇

【Construct Binary Tree from Inorder and Postorder Traversal】cpp

阅读量：6720 次

发布时间：2019-06-25

本文共 2962 字，大约阅读时间需要 9 分钟。

题目：

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:

You may assume that duplicates do not exist in the tree.

代码：

/** * 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) {        if ( inorder.size()==0 || postorder.size()==0 ) return NULL;        return Solution::buildTreeIP(inorder, 0, inorder.size()-1, postorder, 0, postorder.size()-1);    }    static TreeNode* buildTreeIP(        vector
       
        & inorder,         int bI, int eI,         vector
        
         & postorder,         int bP, int eP )    {        if ( bI > eI ) return NULL;        TreeNode *root = new TreeNode(postorder[eP]);        int rootPosInorder = bI;        for ( int i = bI; i <= eI; ++i )        {            if ( inorder[i]==root->val ) { rootPosInorder=i; break; }        }        int leftSize = rootPosInorder - bI;        int rightSize = eI - rootPosInorder;        root->left = Solution::buildTreeIP(inorder, bI, rootPosInorder-1, postorder, bP, bP+leftSize-1);        root->right = Solution::buildTreeIP(inorder, rootPosInorder+1, eI, postorder, eP-rightSize, eP-1);        return root;    }};

tips：

思路跟Preorder & Inorder一样。

这里要注意：

1. 算左子树和右子树长度时，要在inorder里面算

2. 左子树和右子树长度可能一样，也可能不一样；因此在计算root->left和root->right的时候，要注意如何切vector下标（之前一直当成左右树长度一样，debug了一段时间才AC）

==============================================

第二次过这道题，沿用了之前construct binary tree的思路，代码一次AC。

/** * 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 Solution::build(inorder, 0, inorder.size()-1, postorder, 0, postorder.size()-1);        }        TreeNode* build(            vector
       
        & inorder, int bi, int ei,            vector
        
         & postorder, int bp, int ep)        {            if ( bi>ei || bp>ep) return NULL;            TreeNode* root = new TreeNode(postorder[ep]);            int right_range = ei - Solution::findPos(inorder, bi, ei, postorder[ep]);            int left_range = ei - bi - right_range;            root->left = Solution::build(inorder, bi, ei-right_range-1, postorder, bp, ep-right_range-1);            root->right = Solution::build(inorder, bi+left_range+1 , ei, postorder, bp+left_range, ep-1);            return root;        }        int findPos(vector
         
          & order, int begin, int end, int val)        {            for ( int i=begin; i<=end; ++i ) if (order[i]==val) return i;        }};