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.

和construct binary tree from inorder and postorder traversal 的构造方法是一样的。

http://blog.csdn.net/kenden23/article/details/15500733

这次是使用preorder数组定位跟节点,利用inorder数组分左右子树。

关键点:

1 定位每层的根节点

2 计算好offset

//2014-2-16 update TreeNode *buildTree(vector &preorder, vector &inorder) { return build(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1); } TreeNode *build(vector &preorder, int pre1, int pre2, vector &inorder, int in1, int in2) { if (pre1 > pre2) return nullptr; TreeNode *root = new TreeNode(preorder[pre1]); int offset = 0; for ( ; inorder[in1+offset] != preorder[pre1]; offset++); root->left = build(preorder, pre1+1, pre1+offset, inorder, in1, in1+offset-1); root->right = build(preorder, pre1+offset+1, pre2, inorder, in1+offset+1, in2); return root; }

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:hdu1251 统计难题(字典树)
下一篇:设计模式(C++版)之(prototype) 原型模式
相关文章

LeetCode题目9 Count and Say

[LeetCode] Best Time to Buy an

[leetcode]Implement strStr()

leetcode代码分类汇总之-树

[LeetCode]Convert Sorted Array t

[LeetCode]Container With Most Water

[LeetCode]Construct Binary Tree

[LeetCode]Construct Binary Tree

[LeetCode]Merge Sorted Array

[LeetCode]Merge k Sorted Lists

图文推荐
leetcode Construct Binary Tree from Preorder and Inorder Traversal
ZOJ 3640 Help Me
leetcode Construct Binary Tree from Preorder and Inorder Traversal
CF 518C(Anya and
leetcode Construct Binary Tree from Preorder and Inorder Traversal
hdu 1016 Prime R
UVA - 11987 - A

分类:默认分类 时间:2012-01-06 人气:14
本文关键词:
分享到:

相关文章

  • [LeetCode] Flatten Binary Tree to Linked List 2014-03-18

    Given a binary tree, flatten it to a linked list in-place. For example, Given 1 / \ 2 5 / \ \ 3 4 6 The flattened tree should look like: 1 \ 2 \ 3 \ 4 \ 5 \ 6 问题描述:给定一个二叉树,将它变成一个类似上面那样的链表,而且操作要原地进行。 根据上面两个树的样子,可以看到,在链表形式中,节点的左孩子为空,右孩子为先序遍历中当前节点的前一个节点

  • Binary Tree Inorder Traversal -- LeetCode 2013-10-22

    原题链接: http://oj.leetcode.com/problems/binary-tree-inorder-traversal/ 通常,实现二叉树的遍历有两个常用的方法:一是用递归,二是使用栈实现的迭代方法。下面分别介绍。 递归应该最常用的算法,相信大家都了解,算法的时间复杂度是O(n), 而空间复杂度则是递归栈的大小,即O(logn)。代码如下: public ArrayList inorderTraversal(TreeNode root) { ArrayList res = new

  • Binary Tree Preorder Traversal 2013-10-23

    Given a binary tree, return the preorder traversal of its nodes' values. For example: Given binary tree {1,#,2,3}, 1 \ 2 / 3 return [1,2,3]. /** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * Tr

  • leetcod Binary Tree Level Order Traversal II 2012-09-16

    Binary Tree Level Order Traversal II Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root). For example: Given binary tree {3,9,20,#,#,15,7}, 3 / \ 9 20 / \ 15

  • LeetCode | Minimum Depth of Binary Tree 2014-01-20

    题目 Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. 分析 题目很简单,需要尽可能写得精炼。 有递归(DFS,解法1)和非递归(BFS,解法2)两种写法。 解法1 public class MinimumDepthOfBinar

  • LeetCode | Binary Tree Zigzag Level Order Traversal 2014-02-23

    题目 Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between). For example: Given binary tree {3,9,20,#,#,15,7}, 3 / \ 9 20 / \ 15 7 return

  • Leetcode Recover Binary Search Tree 2012-03-06

    Recover Binary Search Tree Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure. Note: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution? c

  • LeetCode | Unique Binary Search Trees II 2014-08-16

    题目 Given n, generate all structurally unique BST's (binary search trees) that store values 1...n. For example, Given n = 3, your program should return all 5 unique BST's shown below. 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3 分析 对树的操作一般都是递归了,这

  • leetcode - Validate Binary Search Tree 2014-10-02

    Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.204 (s). 10 q(s)