首页 > 代码库 > LeetCode - Construct Binary Tree from Preorder and Inorder Traversal
LeetCode - Construct Binary Tree from Preorder and Inorder Traversal
根据二叉树的前序遍历和中序遍历构造二叉树。
思路：前序遍历的第一个节点就是根节点，扫描中序遍历找出根结点，根结点的左边、右边分别为左子树、右子树中序遍历。再计算左子数长度leftLength，前序遍历根结点后的leftLength长度为左子树的前序遍历，剩下的为右子树的前序遍历，代码如下：
1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */10 class Solution11 {12 public:13 TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder)14 {15 if (preorder.size() == 0 || inorder.size() == 0)16 return NULL;17 18 return build(&preorder[0], &preorder[preorder.size()-1], &inorder[0], &inorder[inorder.size()-1]);19 }20 TreeNode *build(int *preStart, int *preEnd, int *inStart, int *inEnd)21 {22 //前序遍历的第一个值为根结点的23 int rootValue = http://www.mamicode.com/*preStart;24 TreeNode *root = new TreeNode(rootValue);25 26 if (preStart == preEnd)27 {28 if (inStart == inEnd && *preStart == *inStart)29 return root;30 else31 cout << "Invalid input." << endl;32 }33 34 //在中序遍历中找到根结点的值35 int *rootInorder = inStart;36 while (rootInorder <= inEnd && *rootInorder != rootValue)37 ++rootInorder;38 if (rootInorder == inEnd && *rootInorder != rootValue)39 cout << "Invalid input." << endl;40 41 int leftLength = rootInorder - inStart;42 int *leftPreEnd = preStart + leftLength;43 if (leftLength > 0)44 {45 //构建左子树46 root->left = build(preStart+1, leftPreEnd, inStart, rootInorder-1);47 }48 if (leftLength < preEnd - preStart)49 {50 //构建右子51 root->right = build(leftPreEnd+1, preEnd, rootInorder+1, inEnd);52 }53 return root;54 }55 };
LeetCode - Construct Binary Tree from Preorder and Inorder Traversal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。