高频算法面试题 5. 树(Tree)

1. 一个重要的结论: 一个有n个结点的树有n-1条边.

2. 树的类型:

• 二叉树 每个结点最多只有两个子结点. 完全二叉树 1. 除了最后一层都是满二叉树. 2. 叶结点靠左排列,先填满左边的.
• 多叉树, 每个结点不止两个,如B+ 树.

3. 树的遍历

• 前序遍历 根-左子树-右子树 (3,9,4,null,2,1,7 )
• 中序遍历 左-根-右 -> [ [4,9,null], 3,[1,2,7] ]

• 后序 左-右-根 ->[ [4,null,9], [1,7,2], 3]

  
  
  (3,9,4,null,2,1,7 )

Selection_219.png

题目

105

image.png

236