LintCode-73.前序遍历和中序遍历树构造二叉树

前序遍历和中序遍历树构造二叉树

根据前序遍历和中序遍历树构造二叉树.

注意事项

你可以假设树中不存在相同数值的节点

样例

给出中序遍历：[1,2,3]和前序遍历：[2,1,3]. 返回如下的树:

  2

/

1  3

标签

二叉树

code

/**

 * Definition of TreeNode:

 * class TreeNode {

 * public:

 *     int val;

 *     TreeNode *left, *right;

 *     TreeNode(int val) {

 *         this->val = val;

 *         this->left = this->right = NULL;

 *     }

 * }

 */

class Solution {

    /**

     *@param preorder : A list of integers that preorder traversal of a tree

     *@param inorder : A list of integers that inorder traversal of a tree

     *@return : Root of a tree

     */

public:

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

        // write your code here

        TreeNode *root = NULL;

        vector<int> preorder_l,preorder_r,inorder_l,inorder_r;

        int i,root_index=0;

        if(preorder.empty()!=1 || inorder.empty()!=1) {

            root = new TreeNode(preorder[0]); //  在前序队列中找根节点

            //  在中序队列中找出根节点位置

            for(i=0; i<inorder.size(); i++) {

                if(preorder[0] == inorder[i])

                    break;

                root_index++;

            }

            //  左右子树的前序、中序队列

            for(i=0; i<root_index; i++) {

                preorder_l.push_back(preorder[i+1]);

                inorder_l.push_back(inorder[i]);

            }

            for(i=root_index+1; i<inorder.size(); i++) {

                preorder_r.push_back(preorder[i]);

                inorder_r.push_back(inorder[i]);

            }

            root->left = buildTree(preorder_l, inorder_l);

            root->right = buildTree(preorder_r, inorder_r);

        }

        return root;

    }

};

巴特西

LintCode-73.前序遍历和中序遍历树构造二叉树

前序遍历和中序遍历树构造二叉树

注意事项

样例

标签

code

最新文章

热门文章