105. Construct Binary Tree from Preorder and Inorder Traversal

2019-11-06 08:50:21

字体：大中小

来源：转载

供稿：网友

问题描述 Given PReorder and inorder traversal of a tree, construct the binary tree.

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

解决思路利用递归建树的思想，找到左右子树的list，然后递归下去，就可以了。

代码

/** * 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) { return helper(preorder,inorder,0,preorder.size()-1,0,inorder.size()-1); } TreeNode* helper(vector<int>& preorder, vector<int>& inorder, int pre_begin, int pre_end, int in_begin, int in_end) { if (pre_end < pre_begin) return NULL; TreeNode *root = new TreeNode(preorder[pre_begin]); int left_len = 0; for (int i = in_begin; i <=in_end; ++i) { if (inorder[i] == preorder[pre_begin]) break; ++left_len; } root->left = helper(preorder,inorder,pre_begin+1,pre_begin+left_len,in_begin,in_begin+left_len-1); root->right = helper(preorder,inorder,pre_begin+left_len+1,pre_end,in_begin+left_len+1,in_end); return root; }};

上一篇：我为什么要写博客

下一篇：清华EMBA课程系列思考之十七(2) -- 公司治理