贰.1.4 二叉树的遍历
对于给定的二叉树如图:
贰.1.4.1 前序遍历
定义
前序遍历首先访问根节点,然后遍历左子树,最后遍历右子树。
文首的图,前序遍历的结果是:12457836
题目
给定一个二叉树,返回它的 前序 遍历。示例:
输入: [1,null,2,3]的树
1 \ 2 / 3
输出: [1,2,3]
代码
递归解法:
迭代解法:
贰.1.4.2 中序遍历
定义
中序遍历是先遍历左子树,然后访问根节点,然后遍历右子树。
文首的图,中序遍历的结果是:42758136
题目
//略
贰.1.4.3 后序遍历
定义
后序遍历是先遍历左子树,然后遍历右子树,最后访问树的根节点。
文首的图,后序遍历的结果是:47852631
题目
//略
贰.1.4.4 层序遍历
文首的图,层序遍历的结果是:12345678
题目
文首的二叉树,请你返回其按 层序遍历 得到的节点值(即逐层地,从左到右访问所有节点)。
返回其层次遍历结果数组:
[[1],[2,3],[4,5,6],[7,8]]
思路
利用队列这个数据结构,将每层的节点放进队列,遍历完当前层的节点之后,再将子节点放到队列进行遍历,直到遍历完所有叶节点。
代码
贰.1.4.5 深度优先与广度优先遍历
其实深度优先遍历也就是前序遍历,广度优先遍历就是层序遍历。
最后更新于