面试题6-重建二叉树

面试题6-重建二叉树

剑指Offer 

基础知识

树是在编程中经常遇到的一种数据结构，它的逻辑结构很简单：除根节点外每个结点都有父节点，除叶子结点外每个结点都有一个或者多个子结点，父节点和子结点通过指针相连。在学习树的结构的时候，多是二叉树，也就是每个结点最多只能有两个子结点。在二叉树中最重要的莫过于遍历。在树的遍历方法中共有先序、中序、后续遍历三种遍历方式，每一种遍历都有递归和循环两种不同的实现方法。同时在树的应用中，又能考察到广度优先搜索、深度优先搜索这两种编程思想，同时二叉搜索树和红黑树、堆都是树的应用。这么说起来觉得树这种结构还是很重要的.

题目

输入某二叉树的先序遍历和中序遍历，请重建出该二叉树。

解题思路及代码

1. 先求出根节点（前序序列第一个元素）。
2. 将根节点带入到中序遍历序列中求出左右子树的中序遍历序列。
3. 通过左右子树的中序序列元素集合位置，带入前序遍历序列可以求出左右子树的前序序列。
4. 左右子树的前序序列第一个元素分别是根节点的左右儿子
5. 求出了左右子树的4种序列可以递归上述步骤

1. /** 

   ---

2. * Definition for binary tree 

   ---

3. * public class TreeNode { 

   ---

4. * int val; 

   ---

5. * TreeNode left; 

   ---

6. * TreeNode right; 

   ---

7. * TreeNode(int x) { val = x; } 

   ---

8. * } 

   ---

9. */ 

   ---

10. public class Solution { 

    ---

11. public TreeNode reConstructBinaryTree(int [] pre,int [] in) { 

    ---

12. int len1 = pre.length, len2 = in.length; 

    ---

13.  

    ---

14. if(len1 != len2 || len1 <= 0) 

    ---

15. return null; 

    ---

16. TreeNode res = getTreeNode(pre, in, 0, len1-1, 0, len2-1); 

    ---

17. return res; 

    ---

18.  

    ---

19. } 

    ---

20. public TreeNode getTreeNode(int[] pre, int[] in, int preStart, int preEnd, int inStart, int inEnd){ 

    ---

21. if( preStart > preEnd || inStart > inEnd) 

    ---

22. return null; 

    ---

23. int val = pre[preStart];//求出根节点 

    ---

24. int pos = -1; 

    ---

25. for(int i = inStart; i<= inEnd; i++){//在中序遍历中查找根节点 

    ---

26. if(val == in[i]){ 

    ---

27. pos = i; 

    ---

28. break; 

    ---

29. } 

    ---

30. } 

    ---

31. if(pos == -1) 

    ---

32. return null; 

    ---

33. TreeNode node = new TreeNode(val); 

    ---

34. //根据中序遍历的根节点位置，重新计算左右子树的先序和中序遍历的序列，重构二叉树。 

    ---

35. node.left = getTreeNode(pre, in, preStart+1, preStart + pos - inStart, inStart, pos-1); 

    ---

36. node.right = getTreeNode(pre, in, preStart + pos - inStart + 1, preEnd, pos+1, inEnd); 

    ---

37. return node; 

    ---

38. } 

    ---

39. } 

    ---