乐趣区

关于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,不必数组,用数组就超时了。

退出移动版