首页 > 代码库 > Construct Binary Tree from Preorder and Inorder Traversal

Construct Binary Tree from Preorder and Inorder Traversal

2024-07-01 23:07:56   228人阅读

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

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

思路：由前序遍历数组和中序遍历数组构建二叉树，此题与Construct Binary Tree from Inorder and Postorder Traversal很相似。

1.从前序遍历找树的根结点，即第一个元素；

2.从中序遍历中查找根结点的位置，并记录下位置，计算出此时的长度len；

3.递归调用函数找出左右子树的根结点；

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void buildBST(TreeNode *&root,vector<int> &preorder,int preBegin,int preEnd,vector<int> &inorder,int inBegin,int inEnd)
    {
        if(preBegin>preEnd||inBegin>inEnd)
            return;
        int pRoot=preorder[preBegin];
        root=new TreeNode(pRoot);
        int index=0;
        for(int i=inBegin;i<=inEnd;i++)
        {
            if(inorder[i]==pRoot)
            {
                index=i;
                break;
            }
        }
        int len=index-inBegin;
        buildBST(root->left,preorder,preBegin+1,preBegin+len,inorder,inBegin,index-1);
        buildBST(root->right,preorder,preBegin+len+1,preEnd,inorder,index+1,inEnd);
    }
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        if(preorder.size()==0||inorder.size()==0)
            return NULL;
        TreeNode *root=NULL;
        int preBegin=0,preEnd=preorder.size()-1;
        int inBegin=0,inEnd=inorder.size()-1;
        buildBST(root,preorder,preBegin,preEnd,inorder,inBegin,inEnd);
        return root;
    }
};

 


联系
我们