关于java:07-重建二叉树

07. 重建二叉树

补充常识：

1、须要定义二叉树类

public class TreeNode {
   int val;
   TreeNode left;// 左节点
   TreeNode right;// 右节点
   TreeNode(int x) {val = x;}
}

2、二叉树的遍历形式
简略来说

前序遍历：根左右:A, B, D, E, C, F, G
中序遍历：左根右:D, B, E, A, F, C, G
后序遍历：左右根:D, E, B, F, G, C, A
层序遍历：按层从左到右拜访:

[[A],
 [B,C],
 [D,E,F,G]
]

二叉树的遍历（前序遍历、中序遍历、后序遍历、层序遍历）
“遇到二叉树，根本是 递归”

思维：

首先 前序失去 根，就能从 中序中分出 左子树和右子树 。分出的左子树，再从 前序失去它的 根，就能从 中序中分出它的 左子树和右子树 ，分出的右子树，再从 前序失去它的 根，就能从 中序中分出它的 左子树和右子树….

总结下来就是，前序失去根，中序分左右子树。
再明确一下左右子的在 中序的范畴，用 left right 来示意；
以及根在 前序的地位 root，和根在 中序的地位 i。

假如一个二叉树,

已知此序的 root,left,right,inorder_root,length=(0,0,8,5,9)

前序：987216543
中序：271869453

• 用前序的根 [9] 分：
  前序：[9],87216543
  中序：[27186],[9],[453]
  分得前序：[9],[87216],[543]
  失去
  左子树 1：前序：87216
  左子树 1：中序：27186

  该序的 root,left,right,inorder_root=(1,0,4,3)(root+1,left,i-1,i)

  右子树 1：前序：543
  右子树 1：中序：453

  该序的 root,left,right,inorder_root=(6,6,8,7)
  (root+(i-left)+1,i+1,right,i)

前面以此类推

• 用左子树 1 的前序的根 [8] 分：
  左子树 1：前序：[8],7216
  左子树 1：中序：[271],[8],[6]
  失去
  左子树 2：前序：721
  左子树 2：中序：271
• 用左子树 2 的前序的根 [7] 分：
  左子树 2：前序：[7],21
  左子树 2：中序：[2],[7],[1]

以此类推右子树。
但始终都以最开始的序列为参考写索引地位。

操作：

• 留神：
  1、把中序装入 HashMap，且数字是键值（不能反复）, 索引是内容。
  2、判断 left>right 就是 null，
  3、HashMap 失去键值的办法 get(val)
  一个优化思路：用 HashMap，不必数组，用数组就超时了。