【面试算法】——二叉树(一)
一、二叉树问题概述
二叉树类型的题目为常考题型
原因:
- 能够结合队列、栈、链表、字符串等多数据结构
- 需要掌握图的基本遍历方法,比如BFS和DFS
- 需要掌握递归函数的使用,并自己设计出递归过程
- 二叉树问题与实际工作结合紧密
二、二叉树先序,中序和后序遍历
先序遍历:先遍历头节点,再遍历左子树,再遍历右子树
中序遍历:先遍历左子树,再遍历头节点,再遍历右子树
后序遍历:先遍历左子树,再遍历右子树,再遍历头节点
先序遍历
递归实现逻辑
非递归实现逻辑
中序遍历
递归实现
非递归实现
后序遍历
递归实现
非递归实现
复杂度
三种遍历的非递归算法的时间复杂度为O(N),空间复杂度为O(L),N为二叉树的节点数,L为二叉树的层数