首页 > 数据结构 > 树形结构 > LeetCode-Construct Binary Tree from Preorder and Inorder Traversal[二叉树]
2014
11-19

LeetCode-Construct Binary Tree from Preorder and Inorder Traversal[二叉树]

Construct Binary Tree from Preorder and Inorder Traversal

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

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

标签: Tree Array Depth-first Search
分析

代码1

// LeetCode, Construct Binary Tree from Preorder and Inorder Traversal
// 递归,时间复杂度O(n),空间复杂度O(\logn)
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return buildTree(begin(preorder), end(preorder),
                begin(inorder), end(inorder));
    }

    template<typename InputIterator>
    TreeNode* buildTree(InputIterator pre_first, InputIterator pre_last,
            InputIterator in_first, InputIterator in_last) {
        if (pre_first == pre_last) return nullptr;
        if (in_first == in_last) return nullptr;

        auto root = new TreeNode(*pre_first);

        auto inRootPos = find(in_first, in_last, *pre_first);
        auto leftSize = distance(in_first, inRootPos);

        root->left = buildTree(next(pre_first), next(pre_first,
                leftSize + 1), in_first, next(in_first, leftSize));
        root->right = buildTree(next(pre_first, leftSize + 1), pre_last,
                next(inRootPos), in_last);

        return root;
    }
};

Java代码:

class Solution:
    # @param preorder, a list of integers
    # @param inorder, a list of integers
    # @return a tree node
    def buildTree(self, preorder, inorder):
        def buildTreeUtil(preorder,inorder, pstart, istart, len):
            # print(pstart," : " , istart," : ", len)
            if len < 1: return None
            if len == 1: return TreeNode(preorder[pstart])

            midIndex = 0
            for i in range(0,len):
                if inorder[i+istart] == preorder[pstart]:
                    midIndex = i
                    break

            root = TreeNode(preorder[pstart])
            # print("root,",root.val)
            root.left = buildTreeUtil(preorder, inorder, pstart+1, istart, midIndex)
            root.right = buildTreeUtil(preorder,inorder, pstart+midIndex+1,istart+midIndex+1, len-midIndex-1)
            return root
        return buildTreeUtil(preorder,inorder,0,0,len(preorder))

相关题目
Construct Binary Tree from Inorder and Postorder Traversal


  1. 1980年代连续穿过多个中东国家的边境,本身就很高危了。而且你还要突破巴基斯坦空军的防护。关键的是轰炸完了还指望巴基斯坦的F-16无动于衷。我觉得这事就不太靠谱。

  2. 1980年代连续穿过多个中东国家的边境,本身就很高危了。而且你还要突破巴基斯坦空军的防护。关键的是轰炸完了还指望巴基斯坦的F-16无动于衷。我觉得这事就不太靠谱。

  3. 1980年代连续穿过多个中东国家的边境,本身就很高危了。而且你还要突破巴基斯坦空军的防护。关键的是轰炸完了还指望巴基斯坦的F-16无动于衷。我觉得这事就不太靠谱。

  4. 1980年代连续穿过多个中东国家的边境,本身就很高危了。而且你还要突破巴基斯坦空军的防护。关键的是轰炸完了还指望巴基斯坦的F-16无动于衷。我觉得这事就不太靠谱。

  5. 1980年代连续穿过多个中东国家的边境,本身就很高危了。而且你还要突破巴基斯坦空军的防护。关键的是轰炸完了还指望巴基斯坦的F-16无动于衷。我觉得这事就不太靠谱。

  6. 1980年代连续穿过多个中东国家的边境,本身就很高危了。而且你还要突破巴基斯坦空军的防护。关键的是轰炸完了还指望巴基斯坦的F-16无动于衷。我觉得这事就不太靠谱。

  7. 1980年代连续穿过多个中东国家的边境,本身就很高危了。而且你还要突破巴基斯坦空军的防护。关键的是轰炸完了还指望巴基斯坦的F-16无动于衷。我觉得这事就不太靠谱。

  8. 1980年代连续穿过多个中东国家的边境,本身就很高危了。而且你还要突破巴基斯坦空军的防护。关键的是轰炸完了还指望巴基斯坦的F-16无动于衷。我觉得这事就不太靠谱。

  9. 1980年代连续穿过多个中东国家的边境,本身就很高危了。而且你还要突破巴基斯坦空军的防护。关键的是轰炸完了还指望巴基斯坦的F-16无动于衷。我觉得这事就不太靠谱。

  10. 1980年代连续穿过多个中东国家的边境,本身就很高危了。而且你还要突破巴基斯坦空军的防护。关键的是轰炸完了还指望巴基斯坦的F-16无动于衷。我觉得这事就不太靠谱。

  11. 1980年代连续穿过多个中东国家的边境,本身就很高危了。而且你还要突破巴基斯坦空军的防护。关键的是轰炸完了还指望巴基斯坦的F-16无动于衷。我觉得这事就不太靠谱。

  12. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。

  13. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!