二叉树的遍历大冒险
〇、前言
01 文章内容
- 一般提到二叉树的遍历，我们是在说
- 前序遍历、中序遍历、后序遍历和层序遍历
- 或者说三序遍历+层序遍历，毕竟三序和层序的遍历逻辑相差比较大
- 下面讨论三序遍历的递归方法、非递归方法和非递归迭代的统一方法
- 然后再讨论一下层序的一般迭代方法（通过队列）
02 力扣网址
一、前序遍历
01 递归实现
- 递归的基本逻辑是比较简单的，但是注意根据题目的需求不同，实现方式是存在差异的
- 如果题目要求主函数返回一个结果列表，那么就要构造一个辅助函数来帮助实现
- 如果题目只要求函数打印前序遍历的序列，那么一个函数就足够了
(1) 返回列表版本1
返回列表版本：辅助函数携带结果列表
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
inorderTraversalHelper(root,result);
return result;
}
void preorderTraversalHelper(TreeNode root,List<Integer> result){
if(root == null) return;
result.add(root.val);
inorderTraversalHelper(root.left,result);
inorderTraversalHelper(root.right,result);
return;
}
(2) 返回列表版本2
返回列表版本：设置全局变量
List<Integer> result = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
inorderTraversalHelper(root,result);
return result;
}
void preorderTraversalHelper(TreeNode root){
if(root == null) return;
result.add(root.val);
inorderTraversalHelper(root.left,result);
inorderTraversalHelper(root.right,result);
return;
}
(3) 纯真打印版本
void preorderTraversal(TreeNode root){
if(root == null) return;
System.out.print(root.val);
inorderTraversalHelper(root.left,result);
inorderTraversalHelper(root.right,result);
return;
}
02 非递归实现
(1) 一般迭代法
(2) 统一迭代法
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode subRoot = new TreeNode();
if (root != null) stack.push(root); //将根结点入栈
while(!stack.isEmpty()){
subRoot = stack.pop(); //弹出获取栈顶结点
if(subRoot != null){
//===右===
if(subRoot.right != null){
// 添加右结点（空结点不入栈）
stack.push(subRoot.right);
}
//===左===
if(subRoot.left != null){
// 添加左节点（空结点不入栈）
stack.push(subRoot.left);
}
//===中===
stack.push(subRoot); // 添加中结点
stack.push(null); // 中结点访问过，但是还没有处理，加入空结点做为标记。
}else{ // 只有遇到空结点的时候，才将下一个结点放进结果集
result.add(stack.pop().val); //重新取出栈中元素，加入到结果集
}
}
return result;
}
二、中序遍历
01 递归实现
(1) 返回列表版本1
返回列表版本：辅助函数携带结果列表
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
inorderTraversalHelper(root,result);
return result;
}
void preorderTraversalHelper(TreeNode root,List<Integer> result){
if(root == null) return;
inorderTraversalHelper(root.left,result);
result.add(root.val);
inorderTraversalHelper(root.right,result);
return;
}
(2) 返回列表版本2
返回列表版本：设置全局变量
List<Integer> result = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
inorderTraversalHelper(root,result);
return result;
}
void preorderTraversalHelper(TreeNode root){
if(root == null) return;
inorderTraversalHelper(root.left,result);
result.add(root.val);
inorderTraversalHelper(root.right,result);
return;
}
(3) 纯真打印版本
void preorderTraversal(TreeNode root){
if(root == null) return;
inorderTraversalHelper(root.left,result);
System.out.print(root.val);
inorderTraversalHelper(root.right,result);
return;
}
02 非递归实现
(1) 一般迭代法
void inOrderNonRecur(){
Stack<TreeNode> stack = new Stack<>();
TreeNode subRoot = root;
if (subRoot != null) {
while (!stack.isEmpty() || subRoot != null) {
if (subRoot != null) {
stack.push(subRoot);
subRoot = subRoot.left;
} else {
subRoot = stack.pop();
System.out.print("【"+subRoot.val+"】");
subRoot = subRoot.right;
}
}
}
}
(2) 统一迭代法
带注释版本
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode subRoot = new TreeNode();
if (root != null) stack.push(root);
while (!stack.isEmpty()) {
subRoot = stack.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
if (subRoot != null) {
//===右===
if(subRoot.right != null){
// 添加右节点（空节点不入栈）
stack.push(subRoot.right);
}
//===中===
stack.push(subRoot); // 添加中节点
stack.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。
//===左===
if(subRoot.left != null){
// 添加左节点（空节点不入栈）
stack.push(subRoot.left);
}
} else { // 只有遇到空节点的时候，才将下一个节点放进结果集
result.add(stack.pop().val); // 加入到结果集
}
}
return result;
}
无注释版本
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode subRoot = new TreeNode();
if (root != null) stack.push(root);
while (!stack.isEmpty()) {
subRoot = stack.pop();
if (subRoot != null) {
if(subRoot.right != null) stack.push(subRoot.right);
stack.push(subRoot);
stack.push(null);
if(subRoot.left != null) stack.push(subRoot.left);
} else {
result.add(stack.pop().val);
}
}
return result;
}
三、后序遍历
01 递归实现
(1) 返回列表版本1
返回列表版本：辅助函数携带结果列表
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
inorderTraversalHelper(root,result);
return result;
}
void preorderTraversalHelper(TreeNode root,List<Integer> result){
if(root == null) return;
inorderTraversalHelper(root.left,result);
inorderTraversalHelper(root.right,result);
result.add(root.val);
return;
}
(2) 返回列表版本2
返回列表版本：设置全局变量
List<Integer> result = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
inorderTraversalHelper(root,result);
return result;
}
void preorderTraversalHelper(TreeNode root){
if(root == null) return;
inorderTraversalHelper(root.left,result);
inorderTraversalHelper(root.right,result);
result.add(root.val);
return;
}
(3) 纯真打印版本
void preorderTraversal(TreeNode root){
if(root == null) return;
inorderTraversalHelper(root.left,result);
inorderTraversalHelper(root.right,result);
System.out.print(root.val);
return;
}
02 非递归实现
(1) 一般迭代法
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root != null) {
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
TreeNode subRoot = null;
while (!stack.isEmpty()) {
subRoot = stack.peek();
if (subRoot.left != null && root != subRoot.left && root != subRoot.right) {
stack.push(subRoot.left);
} else if (subRoot.right != null && root != subRoot.right) {
stack.push(subRoot.right);
} else {
result.add(stack.pop().val);
root = subRoot;
}
}
}
return result;
}
(2) 双栈迭代法
public List<Integer> postOrderNonRecurByTwoStack(){
List<Integer> result = new ArrayList<>();
TreeNode subRoot = root;
if (subRoot != null) {
Stack<TreeNode> s1 = new Stack<TreeNode>();
Stack<TreeNode> s2 = new Stack<TreeNode>();
s1.push(subRoot);
while (!s1.isEmpty()) {
subRoot = s1.pop();
s2.push(subRoot);
if (subRoot.left != null) {
s1.push(subRoot.left);
}
if (subRoot.right != null) {
s1.push(subRoot.right);
}
}
while (!s2.isEmpty()) {
result.add(s2.pop().val);
}
}
}
(3) 统一迭代法
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode subRoot = new TreeNode();
if (root != null) stack.push(root); //将根结点入栈
while(!stack.isEmpty()){
subRoot = stack.pop(); //弹出获取栈顶结点
if(subRoot != null){
//===中===
stack.push(subRoot); // 添加中结点
stack.push(null); // 中结点访问过，但是还没有处理，加入空结点做为标记。
//===右===
if(subRoot.right != null){
// 添加右结点（空结点不入栈）
stack.push(subRoot.right);
}
//===左===
if(subRoot.left != null){
// 添加左节点（空结点不入栈）
stack.push(subRoot.left);
}
}else{ // 只有遇到空结点的时候，才将下一个结点放进结果集
result.add(stack.pop().val); //重新取出栈中元素，加入到结果集
}
}
return result;
}
四、层序遍历
01 不分层输出
class Solution {
public int[] levelOrder(TreeNode root) {
//if(root == null) return new int[]{};
ArrayList<Integer> result = new ArrayList<Integer>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
TreeNode subRoot = new TreeNode();
if(root != null) queue.offer(root);
while(!queue.isEmpty()){
subRoot = queue.poll();
result.add(subRoot.val);
if(subRoot.left != null) queue.add(subRoot.left);
if(subRoot.right != null) queue.add(subRoot.right);
}
int[] dest = new int[result.size()];
for(int i = 0 ; i < result.size() ; i++){
dest[i] = result.get(i);
}
return dest;
}
}
02 分层输出
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<List<Integer>>();
if (root == null) {
return ret;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while (!queue.isEmpty()) {
List<Integer> level = new ArrayList<Integer>();
int currentLevelSize = queue.size();
for (int i = 1; i <= currentLevelSize; ++i) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
ret.add(level);
}
return ret;
}