概念
二叉树(binary tree)是指树中节点的度不大于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]
代码实现
前序遍历
1.递归
1 | interface TreeNode { |
2.迭代
1 | function preOrderIteration(root: TreeNode): TreeNode[]{ |
中序遍历
1.递归
1 | let list: TreeNode[] = []; |
2.迭代
1 | function cenOrderIteration(root: TreeNode): TreeNode[]{ |
后序遍历
1.递归
1 | let list: TreeNode[] = []; |
2.迭代
1 | function aftOrderIteration(root: TreeNode): TreeNode[]{ |
层级遍历
1 | function layerIteration(root: TreeNode): TreeNode[]{ |