105. Construct Binary Tree from Preorder and Inorder Traversal

Posted on | Edited on | In , |

题目

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/

想法

经典题目，思路是清楚的，就是具体怎么写需要想想

反正是建树，递归做

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 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* helper(vector<int>::iterator prebegin, vector<int>::iterator preend, vector<int>::iterator inbegin, vector<int>::iterator inend) {
        if (prebegin == preend)
            return NULL;
        TreeNode *root = new TreeNode(*prebegin);
        auto inmid = std::find(inbegin, inend, *prebegin);
        root->left = helper(prebegin + 1, prebegin + (inmid - inbegin) + 1, inbegin, inmid);
        root->right = helper(prebegin + (inmid - inbegin) + 1, preend , inmid + 1, inend);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return helper(preorder.begin(), preorder.end(), inorder.begin(), inorder.end());
    }
};

回顾

一次AC

这算是一次对C++的vector与iterator操作的熟悉吧，如何传递一个子的vector，需要iterator来帮助
如果用python做，肯定超省劲

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        if not inorder:
            return
        mid = preorder.pop(0)
        idx = inorder.index(mid)
        root = TreeNode(mid)
        root.left = self.buildTree(preorder, inorder[:idx])
        root.right = self.buildTree(preorder, inorder[idx + 1:])
        
        return root