LeetCode——Construct Binary Tree from Preorder and Inorder Traversal

发布时间:2017-7-1 11:07:07编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"LeetCode——Construct Binary Tree from Preorder and Inorder Traversal ",主要涉及到LeetCode——Construct Binary Tree from Preorder and Inorder Traversal 方面的内容,对于LeetCode——Construct Binary Tree from Preorder and Inorder Traversal 感兴趣的同学可以参考一下。

Question

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

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

Solution

参考:http://www.cnblogs.com/zhonghuasong/p/7096150.html

Code

/** * 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>& preorder, vector<int>& inorder) {        if (preorder.size() == 0 || inorder.size() == 0)            return NULL;                    return ConstructTree(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);    }        TreeNode* ConstructTree(vector<int>& preorder, vector<int>& inorder,             int pre_start, int pre_end, int in_start, int in_end) {        int rootValue = preorder[pre_start];        TreeNode* root = new TreeNode(rootValue);        if (pre_start == pre_end) {            if (in_start == in_end)                return root;        }                int rootIn = in_start;        while (rootIn <= in_end && inorder[rootIn] != rootValue)            rootIn++;                    int preLeftLength = rootIn - in_start;        if (preLeftLength > 0) {            root->left = ConstructTree(preorder, inorder, pre_start + 1, preLeftLength, in_start, rootIn - 1);        }        // 左子树的对大长度就是in_end - in_start        if (preLeftLength < in_end - in_start) {            root->right = ConstructTree(preorder, inorder, pre_start + 1 + preLeftLength, pre_end, rootIn + 1, in_end);        }


上一篇:【七】定制数据对象
下一篇:postsharp的使用:在方法进入/成功/失败/退出时获取方法名和参数值

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款