【LeetCode】144. Binary Tree Preorder Traversal 二叉树先序遍历的非递归实现

本文主要是介绍【LeetCode】144. Binary Tree Preorder Traversal 二叉树先序遍历的非递归实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目

翻译:给定一个二叉树,返回先序遍历的序列。


分析:二叉树的先序遍历、中序遍历及后序遍历算法是数据结构中最基础的遍历算法。

            先序遍历:先访问根节点的数据,再访问左孩子节点的数据,最后访问右孩子节点的数据。图中例子先序遍历输出的序列为:【1,2,3】。

            中序遍历:先访问左孩子节点的数据,再访问根节点的数据,最后访问右孩子节点的数据。图中例子中序遍历输出的序列为:【1,3,2】。

            后序遍历:先访问左孩子节点的数据,再访问右孩子节点的数据,最后访问根节点的数据。图中例子后序遍历输出的序列为:【3,2,1】。

      

            这三种遍历算法若用递归来写是非常简单的,但是如果采用非递归的方式来实现,相对比较复杂。

            以先序遍历为例,可以使用栈的数据结构来实现先序遍历的非递归方法。具体操作如下:

                   1.若二叉树为空,则返回空序列,结束;若不为空,转2;

                   2.新建一个空栈,将根节点加入栈中;

                   3.若栈不为空,取出栈顶节点,访问该节点的数据(将栈顶元素加入返回的序列中);

                      判断该节点的【右节点】是否为空,若不为空,将该节点的右节点加入到栈中;

                      判断该节点的【左节点】是否为空,若不为空,将该节点的左节点加入到栈中;

                    (注意:此处是先判断右节点,再判断左节点,因为栈的特点是“后进先出”,左节点总在右节点先遍历,所以要后加入栈中。)

                   4.重复3,直到栈为空,返回最终得到的先序遍历序列。

代码

         在下面的代码中使用了C#中的List来实现一个栈。

/*** Definition for a binary tree node.* public class TreeNode {*     public int val;*     public TreeNode left;*     public TreeNode right;*     public TreeNode(int x) { val = x; }* }*/
public class Solution {public IList<int> PreorderTraversal(TreeNode root) {List<int> results=new List<int>();if(root==null)return results;List<TreeNode> stack=new List<TreeNode>();//新建一个队列stack.Add(root);while(stack.Count()!=0)//若栈不为空,取出栈顶元素,访问数值,判断左右孩子是否为空,若不为空,加入栈,先加右孩子,再加左孩子{TreeNode temp=stack.Last();//取出栈顶元素stack.Remove(stack.Last());//移除results.Add(temp.val);if(temp.right!=null)stack.Add(temp.right);if(temp.left!=null)stack.Add(temp.left);}return results;}
}


             

这篇关于【LeetCode】144. Binary Tree Preorder Traversal 二叉树先序遍历的非递归实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/902388

相关文章

Python实现批量提取BLF文件时间戳

《Python实现批量提取BLF文件时间戳》BLF(BinaryLoggingFormat)作为Vector公司推出的CAN总线数据记录格式,被广泛用于存储车辆通信数据,本文将使用Python轻松提取... 目录一、为什么需要批量处理 BLF 文件二、核心代码解析:从文件遍历到数据导出1. 环境准备与依赖库

linux下shell脚本启动jar包实现过程

《linux下shell脚本启动jar包实现过程》确保APP_NAME和LOG_FILE位于目录内,首次启动前需手动创建log文件夹,否则报错,此为个人经验,供参考,欢迎支持脚本之家... 目录linux下shell脚本启动jar包样例1样例2总结linux下shell脚本启动jar包样例1#!/bin

go动态限制并发数量的实现示例

《go动态限制并发数量的实现示例》本文主要介绍了Go并发控制方法,通过带缓冲通道和第三方库实现并发数量限制,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面... 目录带有缓冲大小的通道使用第三方库其他控制并发的方法因为go从语言层面支持并发,所以面试百分百会问到

Go语言并发之通知退出机制的实现

《Go语言并发之通知退出机制的实现》本文主要介绍了Go语言并发之通知退出机制的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录1、通知退出机制1.1 进程/main函数退出1.2 通过channel退出1.3 通过cont

Python实现PDF按页分割的技术指南

《Python实现PDF按页分割的技术指南》PDF文件处理是日常工作中的常见需求,特别是当我们需要将大型PDF文档拆分为多个部分时,下面我们就来看看如何使用Python创建一个灵活的PDF分割工具吧... 目录需求分析技术方案工具选择安装依赖完整代码实现使用说明基本用法示例命令输出示例技术亮点实际应用场景扩

java如何实现高并发场景下三级缓存的数据一致性

《java如何实现高并发场景下三级缓存的数据一致性》这篇文章主要为大家详细介绍了java如何实现高并发场景下三级缓存的数据一致性,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 下面代码是一个使用Java和Redisson实现的三级缓存服务,主要功能包括:1.缓存结构:本地缓存:使

如何在Java Spring实现异步执行(详细篇)

《如何在JavaSpring实现异步执行(详细篇)》Spring框架通过@Async、Executor等实现异步执行,提升系统性能与响应速度,支持自定义线程池管理并发,本文给大家介绍如何在Sprin... 目录前言1. 使用 @Async 实现异步执行1.1 启用异步执行支持1.2 创建异步方法1.3 调用

Spring Boot配置和使用两个数据源的实现步骤

《SpringBoot配置和使用两个数据源的实现步骤》本文详解SpringBoot配置双数据源方法,包含配置文件设置、Bean创建、事务管理器配置及@Qualifier注解使用,强调主数据源标记、代... 目录Spring Boot配置和使用两个数据源技术背景实现步骤1. 配置数据源信息2. 创建数据源Be

在MySQL中实现冷热数据分离的方法及使用场景底层原理解析

《在MySQL中实现冷热数据分离的方法及使用场景底层原理解析》MySQL冷热数据分离通过分表/分区策略、数据归档和索引优化,将频繁访问的热数据与冷数据分开存储,提升查询效率并降低存储成本,适用于高并发... 目录实现冷热数据分离1. 分表策略2. 使用分区表3. 数据归档与迁移在mysql中实现冷热数据分

linux批量替换文件内容的实现方式

《linux批量替换文件内容的实现方式》本文总结了Linux中批量替换文件内容的几种方法,包括使用sed替换文件夹内所有文件、单个文件内容及逐行字符串,强调使用反引号和绝对路径,并分享个人经验供参考... 目录一、linux批量替换文件内容 二、替换文件内所有匹配的字符串 三、替换每一行中全部str1为st