06_重建二叉树

缺乏、安全感 2022-06-16 09:53 54阅读 0赞

题目:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列1,2,4,7,3,5,6,8和中序遍历序列4,7,2,1,5,3,8,6,则重建二叉树并返回。

Java版本:

  1. public class new1 {
  2. /**
  3. * 二叉树节点类
  4. */
  5. public static class BinaryTreeNode {
  6. int Value;
  7. BinaryTreeNode Left;
  8. BinaryTreeNode Right;
  9. }
  10. /**
  11. * 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二节树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
  12. *
  13. * @param preOrder 前序遍历
  14. * @param inOrder 中序遍历
  15. * @return 树的根结点
  16. */
  17. public static BinaryTreeNode construct(int[] preOrder, int[] inOrder) {
  18. // 输入的合法性判断,两个数组都不能为空,并且都有数据,而且数据的数目相同
  19. if (preOrder == null || inOrder == null || preOrder.length != inOrder.length || inOrder.length < 1) {
  20. return null;
  21. }
  22. return construct(preOrder, 0, preOrder.length - 1, inOrder, 0, inOrder.length - 1);
  23. }
  24. /**
  25. * 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二节树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
  26. *
  27. * @param preOrder 前序遍历
  28. * @param preStart 前序遍历的开始位置
  29. * @param preEnd 前序遍历的结束位置
  30. * @param inOrder 中序遍历
  31. * @param inStart 中序遍历的开始位置
  32. * @param inEnd 中序遍历的结束位置
  33. * @return 树的根结点
  34. */
  35. public static BinaryTreeNode construct(int[] preOrder, int preStart, int preEnd, int[] inOrder, int inStart, int inEnd) {
  36. // 开始位置大于结束位置说明已经没有需要处理的元素了
  37. if (preStart > preEnd) {
  38. return null;
  39. }
  40. // 取前序遍历的第一个数字,就是当前的根结点
  41. int rootValue = preOrder[preStart];
  42. int index = inStart;
  43. // 在中序遍历的数组中找根结点的位置
  44. while (index <= inEnd && inOrder[index] != rootValue) {
  45. index++;
  46. }
  47. // 如果在整个中序遍历的数组中没有找到,说明输入的参数是不合法的,抛出异常
  48. if (index > inEnd) {
  49. throw new RuntimeException("Invalid input");
  50. }
  51. // 创建当前的根结点,并且为结点赋值
  52. BinaryTreeNode node = new BinaryTreeNode();
  53. node.Value = rootValue;
  54. // 递归构建当前根结点的左子树,左子树的元素个数:index-inStart+1个
  55. // 左子树对应的前序遍历的位置在[preStart+1, preStart+index-inStart]
  56. // 左子树对应的中序遍历的位置在[inStart, index-1]
  57. node.Left = construct(preOrder, preStart + 1, preStart + index - inStart, inOrder, inStart, index - 1);
  58. // 递归构建当前根结点的右子树,右子树的元素个数:inEnd-index个
  59. // 右子树对应的前序遍历的位置在[preStart+index-inStart+1, preEnd]
  60. // 右子树对应的中序遍历的位置在[index+1, inEnd]
  61. node.Right = construct(preOrder, preStart + index - inStart + 1, preEnd, inOrder, index + 1, inEnd);
  62. // 返回创建的根结点
  63. return node;
  64. }
  65. public static void printTreeNode(BinaryTreeNode Node){
  66. if(Node != null)
  67. {
  68. System.out.println("value of this node is:"+ Node.Value);
  69. if(Node.Left != null)
  70. System.out.println("value of its left child is: "+Node.Left.Value);
  71. else
  72. System.out.println("left child is null");
  73. if(Node.Right != null)
  74. System.out.println("value of its right child is:"+Node.Right.Value);
  75. else
  76. System.out.println("right child is null");
  77. }
  78. else
  79. {
  80. System.out.println("this node is null");
  81. }
  82. System.out.println();
  83. }
  84. public static void printTree(BinaryTreeNode root) {
  85. printTreeNode(root);
  86. if(root != null)
  87. {
  88. if(root.Left != null)
  89. printTree(root.Left);
  90. if(root.Right != null)
  91. printTree(root.Right);
  92. }
  93. }
  94. public static void Test(String testName, int[] preorder, int[] inorder){
  95. int length = preorder.length;
  96. if(testName != null)
  97. System.out.println(testName+" begins:");
  98. System.out.println("The preorder sequence is: ");
  99. for(int i = 0; i < length; ++ i)
  100. System.out.print(preorder[i]+" ");
  101. System.out.println();
  102. System.out.println("The inorder sequence is: ");
  103. for(int i = 0; i < length; ++ i)
  104. System.out.print(inorder[i]+" ");
  105. System.out.println("\n");
  106. BinaryTreeNode root = construct(preorder, inorder);
  107. printTree(root);
  108. }
  109. // 普通二叉树
  110. // 1
  111. // / \
  112. // 2 3
  113. // / / \
  114. // 4 5 6
  115. // \ /
  116. // 7 8
  117. private static void Test1() {
  118. int[] preOrder = {
  119. 1, 2, 4, 7, 3, 5, 6, 8};
  120. int[] inOrder = {
  121. 4, 7, 2, 1, 5, 3, 8, 6};
  122. Test("Test1", preOrder, inOrder);
  123. }
  124. // 所有结点都没有右子结点
  125. // 1
  126. // /
  127. // 2
  128. // /
  129. // 3
  130. // /
  131. // 4
  132. // /
  133. // 5
  134. // private static void Test2() {
  135. // int[] preOrder = {1, 2, 3, 4, 5};
  136. // int[] inOrder = {5, 4, 3, 2, 1};
  137. // Test("Test2", preOrder, inOrder);
  138. // }
  139. // 所有结点都没有左子结点
  140. // 1
  141. // \
  142. // 2
  143. // \
  144. // 3
  145. // \
  146. // 4
  147. // \
  148. // 5
  149. // private static void Test3() {
  150. // int[] preOrder = {1, 2, 3, 4, 5};
  151. // int[] inOrder = {1, 2, 3, 4, 5};
  152. // Test("Test3", preOrder, inOrder);
  153. // }
  154. // 树中只有一个结点
  155. // private static void Test4() {
  156. // int[] preOrder = {1};
  157. // int[] inOrder = {1};
  158. // Test("Test4", preOrder, inOrder);
  159. // }
  160. // 完全二叉树
  161. // 1
  162. // / \
  163. // 2 3
  164. // / \ / \
  165. // 4 5 6 7
  166. // private static void Test5() {
  167. // int[] preOrder = {1, 2, 4, 5, 3, 6, 7};
  168. // int[] inOrder = {4, 2, 5, 1, 6, 3, 7};
  169. // Test("Test5", preOrder, inOrder);
  170. // }
  171. // // 输入的两个序列不匹配
  172. // private static void Test6() {
  173. // int[] preOrder = {1, 2, 4, 5, 3, 6, 7};
  174. // int[] inOrder = {4, 2, 8, 1, 6, 3, 7};
  175. // Test("Test6", preOrder, inOrder);
  176. // }
  177. public static void main(String[] args) {
  178. Test1();
  179. //Test2();
  180. //Test3();
  181. //Test4();
  182. //Test5();
  183. //Test6();
  184. }
  185. }

这里写图片描述
这里写图片描述
这里写图片描述

Python版本:

  1. # -*- coding:utf-8 -*-
  2. # 二叉树节点类
  3. class TreeNode:
  4. def __init__(self,x):
  5. self.Value = x
  6. self.Left = None
  7. self.Right = None
  8. # 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二节树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
  9. # preOrder:前序遍历 inOrder:中序遍历 return:树的根结点
  10. def construct1(preOrder, inOrder):
  11. # 输入的合法性判断,两个数组都不能为空,并且都有数据,而且数据的数目相同
  12. if (preOrder == None or inOrder == None or len(preOrder) != len(inOrder) or len(inOrder) < 1):
  13. return None
  14. return construct2(preOrder, 0, len(preOrder) - 1, inOrder, 0, len(inOrder) - 1)
  15. # 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二节树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
  16. # preStart:前序遍历的开始位置 preEnd:前序遍历的结束位置
  17. # inStart:中序遍历的开始位置 inEnd:中序遍历的结束位置
  18. # 树的根结点
  19. def construct2(preOrder,preStart,preEnd,inOrder,inStart,inEnd):
  20. # 开始位置大于结束位置说明已经没有需要处理的元素了
  21. if (preStart > preEnd):
  22. return None
  23. # 取前序遍历的第一个数字,就是当前的根结点
  24. rootValue = preOrder[preStart]
  25. index = inStart
  26. # 在中序遍历的数组中找根结点的位置
  27. while (index <= inEnd and inOrder[index] != rootValue):
  28. index = index + 1
  29. #如果在整个中序遍历的数组中没有找到,说明输入的参数是不合法的,抛出异常
  30. if (index > inEnd):
  31. raise Exception("Invalid input")
  32. # 创建当前的根结点,并且为结点赋值
  33. node= TreeNode(rootValue)
  34. # 递归构建当前根结点的左子树,左子树的元素个数:index-inStart+1个
  35. # 左子树对应的前序遍历的位置在[preStart+1, preStart+index-inStart]
  36. # 左子树对应的中序遍历的位置在[inStart, index-1]
  37. node.Left = construct2(preOrder, preStart + 1, preStart + index - inStart, inOrder, inStart, index - 1)
  38. # 递归构建当前根结点的右子树,右子树的元素个数:inEnd-index个
  39. # 右子树对应的前序遍历的位置在[preStart+index-inStart+1, preEnd]
  40. # 右子树对应的中序遍历的位置在[index+1, inEnd]
  41. node.Right = construct2(preOrder, preStart + index - inStart + 1, preEnd, inOrder, index + 1, inEnd)
  42. # 返回创建的根结点
  43. return node
  44. def printTreeNode(Node):
  45. print()
  46. if(Node != None):
  47. print("value of this node is:",Node.Value)
  48. if(Node.Left != None):
  49. print("value of its left child is: ",Node.Left.Value)
  50. else:
  51. print("left child is None")
  52. if(Node.Right != None):
  53. print("value of its right child is:",Node.Right.Value)
  54. else:
  55. print("right child is None")
  56. else:
  57. print("this node is None")
  58. def printTree(root):
  59. printTreeNode(root)
  60. if(root != None):
  61. if(root.Left != None):
  62. printTree(root.Left)
  63. if(root.Right != None):
  64. printTree(root.Right)
  65. def Test(testName,preorder,inorder):
  66. length = len(preorder)
  67. if(testName != None):
  68. print(testName," begins:")
  69. print("The preorder sequence is: ",end='')
  70. for i in range(length):
  71. print(preorder[i]," ",end='')
  72. print()
  73. print("The inorder sequence is: ",end='')
  74. for i in range(length):
  75. print(inorder[i]," ",end='')
  76. print()
  77. root = construct1(preorder, inorder)
  78. printTree(root)
  79. # 普通二叉树
  80. # 1
  81. # / \
  82. # 2 3
  83. # / / \
  84. # 4 5 6
  85. # \ /
  86. # 7 8
  87. def Test1():
  88. preOrder = [1, 2, 4, 7, 3, 5, 6, 8]
  89. inOrder = [4, 7, 2, 1, 5, 3, 8, 6]
  90. Test("Test1", preOrder, inOrder)
  91. # 所有结点都没有右子结点
  92. # 1
  93. # /
  94. # 2
  95. # /
  96. # 3
  97. # /
  98. # 4
  99. # /
  100. # 5
  101. def Test2():
  102. preOrder = [1, 2, 3, 4, 5 ]
  103. inOrder = [5, 4, 3, 2, 1 ]
  104. Test("Test2", preOrder, inOrder)
  105. # 树中只有一个结点
  106. def Test3():
  107. preOrder = [ 1 ]
  108. inOrder = [ 1 ]
  109. Test("Test3", preOrder, inOrder)
  110. ## 输入的两个序列不匹配
  111. def Test4():
  112. preOrder = [1, 2, 4, 5, 3, 6, 7 ]
  113. inOrder = [4, 2, 8, 1, 6, 3, 7]
  114. Test("Test4", preOrder, inOrder)
  115. Test1()
  116. Test2()
  117. Test3()
  118. Test4()

这里写图片描述
这里写图片描述

发表评论

表情:
评论列表 (有 0 条评论,54人围观)

还没有评论,来说两句吧...

相关阅读

    相关 06_重建

    > 题目:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列1,2,4,7,3,5,6,8和中

    相关 重建

    二叉树重建 根据二叉树的前序遍历和中序遍历,重建二叉树。综合利用前序遍历和中序遍历的特点。 / 题目描述 输入某二叉树的前序遍历和中序遍历的

    相关 重建

    重建二叉树     输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。如前序\{1,2,4,7,3,5,6,8

    相关 重建

    时间限制:1秒 空间限制:32768K 热度指数:524408 算法知识视频讲解 题目描述 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序

    相关 重建

    题目描述 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6

    相关 重建

    给定二叉树的先序遍历序列和中序遍历序列,进行二叉树的重建以及后序遍历队列。 突然看到这个问题。。发现之前的想法都忘记了=\_=||,果然算法题一日不写手生啊,还是得好好坚持

    相关 重建

    输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,8\}和中序

    相关 重建

    输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,8\}和中序