Leetcode（105）-从前序与中序遍历序列构造二叉树

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

注意:
你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]

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

返回如下的二叉树：

思路：前序遍历先访问根节点，因此前序遍历序列的第一个字母肯定就是根节点；然后，由于中序遍历先访问左子树，再访问根节点，最后访问右子树，所以我们找到中序遍历中根节点的位置，然后它左边的字母就是左子树了；同样的，它右边的就是右子树。

将前序遍历序列也按照中序遍历的分隔分成两部分，分别对左子树和右子树应用同样的方法，递归下去，二叉树就成功构建好了。

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)

 {

     int size = preorder.size();

     if(size==0 || inorder.empty())

     {

         return NULL;

     }

     int r = preorder[0];//在前序遍历中。第一个节点就是我们所求二叉树的根节点

     TreeNode* root = new TreeNode(r);

     int p=0;

     for(;p<size;p++)

     {

         if(inorder[p]==r)//在中序遍历中找到根节点的位置

             break;

     }

     vector<int> pre_left,pre_right,in_left,in_right;

     for(int i=0;i<size;i++)

     {

         if(i<p)

         {

             pre_left.push_back(preorder[i+1]);//前序遍历中，从头到中序遍历的根节点的位置p，这个区间上的点是左子树的前序遍历

             in_left.push_back(inorder[i]);//中序遍历中，从头到根节点的位置p，这个区间的点是左子树的中序遍历

         }

         else if(i>p)

         {

             pre_right.push_back(preorder[i]);//前序遍历中，从位置p到末尾，这个区间是右子树的前序遍历

             in_right.push_back(inorder[i]);//中序遍历中，从位置p到末尾，这个区间是右子树的中序遍历

         }

     }

     root->left = buildTree(pre_left,in_left);//递归实现左子树和右子树的重建过程

     root->right = buildTree(pre_right,in_right);

     return root;

 }

当然还有非递归的方法，也是利用栈来完成的，但是思路不是很好理解。谨附下代码

 TreeNode* buildTree(vector<char>& preorder, vector<char>& inorder) {

        if(preorder.empty()) return NULL;

         TreeNode* t=new TreeNode(preorder[0]),*p=t;

         stack<TreeNode*>  roots;

         int size=preorder.size(), i=0,j=0;

         while(j<size-1)

         {

            // roots.push(p);

             while(preorder[i++]!=inorder[j])

             {

                 p->left=new TreeNode(preorder[i]);

                 roots.push(p);

                 p=p->left;

             }

            if(i==size) break;

            while(++j<size&&!roots.empty()&&inorder[j]==roots.top()->val)

            {

                p=roots.top();

                roots.pop();

            }

             p->right=new TreeNode(preorder[i]);

             p=p->right;

         }

        return t;

    }

巴特西

Leetcode（105）-从前序与中序遍历序列构造二叉树

最新文章

热门文章