LeetCode

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

思路：前序遍历的第一个节点就是根节点，扫描中序遍历找出根结点，根结点的左边、右边分别为左子树、右子树中序遍历。再计算左子数长度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 Solution
11 {
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 = *preStart;
24         TreeNode *root = new TreeNode(rootValue);
25         
26         if (preStart == preEnd)
27         {
28             if (inStart == inEnd && *preStart == *inStart)
29                 return root;
30             else
31                 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 };