庖丁解牛-二叉树的遍历

2024-02-23 10:52
文章标签 二叉树 遍历 庖丁解牛

本文主要是介绍庖丁解牛-二叉树的遍历，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

庖丁解牛-二叉树的遍历

在这里插入图片描述

〇、前言

01 文章内容

  • 一般提到二叉树的遍历，我们是在说
    • 前序遍历、中序遍历、后序遍历和层序遍历
  • 或者说三序遍历+层序遍历，毕竟三序和层序的遍历逻辑相差比较大
  • 下面讨论三序遍历的递归方法、非递归方法和非递归迭代的统一方法
  • 然后再讨论一下层序的一般迭代方法（通过队列）

02 力扣网址

  • 144. 二叉树的前序遍历 - 力扣（LeetCode）
  • 94. 二叉树的中序遍历 - 力扣（LeetCode）
  • 145. 二叉树的后序遍历 - 力扣（LeetCode）

一、前序遍历

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) 纯真打印版本
public List<Integer> preorderTraversal(TreeNode root) {inorderTraversalHelper(root,result);return result;
}
void preorderTraversal(TreeNode root){if(root == null) return;System.out.print(root.val);inorderTraversalHelper(root.left,result);inorderTraversalHelper(root.right,result);return;
}
(4) 面向对象版本
class Solution {class TraverBox{List<Integer> list;TraverBox(){list = new ArrayList<>();}void preorderTraversalHelper(TreeNode root) {list.add(root.val);}void preTraverHelper(TreeNode root) {if(root == null) return;list.add(root.val);preTraverHelper(root.left);preTraverHelper(root.right);}List<Integer> preTraver(TreeNode root) {preTraverHelper(root);return list;}}public List<Integer> preorderTraversal(TreeNode root) {TraverBox tox = new TraverBox();tox.preTraver(root);return tox.list;}
}

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;
}

这篇关于庖丁解牛-二叉树的遍历的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/738377。

相关文章

leetcode105 从前序与中序遍历序列构造二叉树

leetcode105 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如，给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树： 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr
阅读更多...
PHP实现二叉树遍历(非递归方式，栈模拟实现)

PHP实现二叉树遍历(非递归方式，栈模拟实现)

二叉树定义是这样的：一棵非空的二叉树由根结点及左、右子树这三个基本部分组成，根据节点的访问位置不同有三种遍历方式： ① NLR：前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR：中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN：后序遍历(PostorderT
阅读更多...
react笔记 8-17 属性绑定 class绑定 引入图片 循环遍历

react笔记 8-17 属性绑定 class绑定 引入图片 循环遍历

1、绑定属性 constructor(){super()this.state={name:"张三",title:'我是一个title'}}render() {return (<div><div>aaaaaaa{this.state.name}<div title={this.state.title}>我是一个title</div></div></div>)} 绑定属性直接使用花括号{}   注
阅读更多...
在二叉树中找到两个节点的最近公共祖先（基于Java）

在二叉树中找到两个节点的最近公共祖先（基于Java）

如题  题解 public int lowestCommonAncestor(TreeNode root, int o1, int o2) {//记录遍历到的每个节点的父节点。Map<Integer, Integer> parent = new HashMap<>();Queue<TreeNode> queue = new LinkedList<>();parent.put(roo
阅读更多...
数据结构--二叉树（C语言实现，超详细！！！）

数据结构--二叉树（C语言实现，超详细！！！）

文章目录 二叉树的概念代码实现二叉树的定义创建一棵树并初始化组装二叉树前序遍历中序遍历后序遍历计算树的结点个数求二叉树第K层的结点个数求二叉树高度查找X所在的结点查找指定节点在不在完整代码 二叉树的概念 二叉树（Binary Tree）是数据结构中一种非常重要的树形结构，它的特点是每个节点最多有两个子节点，通常称为左子节点和右子节点。这种结构使得二叉树在数据存储和查找等方面具
阅读更多...
hashmap的存值，各种遍历方法

hashmap的存值，各种遍历方法

package com.jefflee;import java.util.HashMap;import java.util.Iterator;import java.util.Map;public class HashmapTest {// 遍历Hashmap的四种方法public static void main(String[] args) {//hashmap可以存一个null，把
阅读更多...
Knight Moves -uva 简单的BFS遍历

Knight Moves -uva 简单的BFS遍历

昨天刚学了BFS的遍历，在uva上找了个题敲了出来，感觉还不错，最近敲代码挺有手感的，希望这种状态保持下去 #include<iostream>#include<stdio.h>#include<stdlib.h>#include<string.h>#define MAX_SIZE 10 + 5#define LEN 100 + 10using namespace std;in
阅读更多...
笔试强训,[NOIP2002普及组]过河卒牛客.游游的水果大礼包牛客.买卖股票的最好时机（二)二叉树非递归前序遍历

笔试强训,[NOIP2002普及组]过河卒牛客.游游的水果大礼包牛客.买卖股票的最好时机（二)二叉树非递归前序遍历

目录 [NOIP2002普及组]过河卒 牛客.游游的水果大礼包 牛客.买卖股票的最好时机（二) 二叉树非递归前序遍历 [NOIP2002普及组]过河卒 题里面给的提示很有用，那个马的关系，后面就注意，dp需要作为long的类型。 import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息publ
阅读更多...
222.完全二叉树的节点个数

222.完全二叉树的节点个数

（写给未来遗忘的自己） 题目： 代码： class Solution {public:int countNodes(TreeNode* root) {queue<TreeNode*>node_que;if(root==nullptr) return 0;node_que.push(root);int result;while(!node_que.empty()){int layer_s
阅读更多...
代码随想录 -- 二叉树 -- 平衡二叉树

代码随想录 -- 二叉树 -- 平衡二叉树

110. 平衡二叉树 - 力扣（LeetCode） 思路：仍然是递归调用 1. 定义一个递归函数 count 用来计算二叉树的层数 2. isBalanced 函数：如果传入根节点为空返回真；如果根节点 | 左子树的层数 - 右子树的层数 | 大于1，返回假；最后返回根节点左子树、右子树是否是平衡二叉树。 class Solution(object):def count(self,root
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2