草庐IT

leetcode 144. Binary Tree Preorder Traversal 二叉树展开为链表(中等)

okokabcd 2023-03-28 原文

一、题目大意

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例 1：

输入：root = [1,null,2,3]

输出：[1,2,3]

示例 2：

输入：root = []

输出：[]

示例 3：

输入：root = [1]

输出：[1]

示例 4：

输入：root = [1,2]

输出：[1,2]

示例 5：

输入：root = [1,null,2]

输出：[1,2]

提示：

  • 树中节点数目在范围 [0, 100] 内

  • -100 <= Node.val <= 100

进阶：递归算法很简单，你可以通过迭代算法完成吗？

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/binary-tree-preorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、解题思路

二叉树的遍历，常见的有先序遍历、中序遍历、后序遍历和层序遍历，它们用uxjv实现起来都非常简单；

考虑使用非递归来实现，用到时stack来辅助转自，由于先序遍历的顺序为 根左右，算法为：

1、把根节点push到栈中

2、循环检查栈是否为空，若不空，取出栈顶元素并保存其值，然后看其右节点是否存在，若存在则push到栈中，再看其左节点，若存在，则push到栈中

三、解题方法

3.1 Java实现-递归

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        // 先序遍历：中左右
        List<Integer> ans = new ArrayList<>();
        preorder(root, ans);
        return ans;
    }

    void preorder(TreeNode node, List<Integer> ans) {
        if (node == null) {
            return;
        }
        ans.add(node.val);
        preorder(node.left, ans);
        preorder(node.right, ans);
    }
}

3.2 Java实现-迭代

public class Solution2 {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        // 使用栈来辅助实现，Java中用双端队列来代替栈
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.addFirst(root);
        while (!stack.isEmpty()) {
            TreeNode tmp = stack.pop();
            ans.add(tmp.val);
            if (tmp.right != null) {
                stack.addFirst(tmp.right);
            }
            if (tmp.left != null) {
                stack.addFirst(tmp.left);
            }
        }
        return ans;
    }
}

四、总结小记

  • 2022/9/23 遇到“上传下达”的情况，激情顿无，毫无意义
Traversalleetcodeblockquotestrongroot算法与数据结构

有关leetcode 144. Binary Tree Preorder Traversal 二叉树展开为链表(中等)的更多相关文章

  1. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  2. ruby - 在 Ruby 中实现二叉树 - 2

    我一直在尝试在Ruby中实现BinaryTree类，但我得到了stackleveltoodeep错误，尽管我似乎没有在该特定代码段中使用任何递归:1.classBinaryTree2.includeEnumerable3.4.attr_accessor:value5.6.definitialize(value=nil)7.@value=value8.@left=BinaryTree.new#stackleveltoodeephere9.@right=BinaryTree.new#andhere10.end11.12.defempty?13.(self.value==nil)?true:

  3. IDEA使用LeetCode插件 - 2

    前言我们习惯用idea编写、调试代码，在LeetCode上刷题时，如果能够在IDEA编写代码，并且做好代码管理，是一件事半功倍的事情。对于后续复习题目，做笔记也会非常便利。本文目的在于介绍LeetCodeEditor的使用，以及配置工具类，最终目录结构如下：note：放置笔记src：放置代码leetcode.editor.cn：插件LeetCodeEditor自动生成utils：自定义的工具包，可用于自动化输入测试用例，定义题目需要的类（结构体）out：运行测试时自动生成LeetCodeEditorGitHub：https://github.com/shuzijun/leetcode-edit

  4. vue 实现内容超出两行显示展开更多功能，可依据需求自定义任意行数！ - 2

    平时开发中我们经常会遇到这样的需求，在一个不限高度的盒子中会有很多内容，如果全部显示用户体验会非常不好，所以可以先折叠起来，当内容达到一定高度时，显示展开更多按钮，点击即可显示全部内容，先来看看效果图： 这样做用户体验瞬间得到提升，接下来看看具体细节。0">主要操作在内容这里{{item.username}},……展开更多样式大家可依据自己项目需求进行设计，这里就不贴了，主要说几个关键的。1、在data中定义三个属性isShowMore:false, //控制展开更多的显示与隐藏textHeight:null, //框中内容的高度status:false, //内容状态是否打开2.计算内容是否

  5. 【数据结构和算法】实现带头双向循环链表（最复杂的链表） - 2

    前文，我们实现了认识了链表这一结构，并实现了无头单向非循环链表，接下来我们实现另一种常用的链表结构，带头双向循环链表。如有仍不了解单向链表的，请看这一篇文章(7条消息)【数据结构和算法】认识线性表中的链表，并实现单向链表_小王学代码的博客-CSDN博客目录前言一、带头双向循环链表是什么？二、实现带头双向循环链表1.结构体和要实现函数2.初始化和打印链表3.头插和尾插4.头删和尾删5.查找和返回结点个数6.在pos位置之前插入结点7.删除指定pos结点8.摧毁链表三、完整代码1.DSLinkList.h2.DSLinkList.c3.test.c总结前言带头双向循环链表，是链表中最为复杂的一种结

  6. vue2+element-ui,el-aside侧边栏容器收缩与展开 - 2

    一、概览实现效果如下：二、项目环境1、nodejs版本node-vv16.16.02、npm版本npm-vnpmWARNconfigglobal`--global`,`--local`aredeprecated.Use`--location=global`instead.8.15.03、vue脚手架版本vue-V@vue/cli5.0.8三、创建vue项目1、创建名为vuetest的项目vuecreatevuetest选择Default（[Vue2]babel,eslint）  2、切换到项目目录，启动项目cdvuetestnpmrunserve 3、使用浏览器预览 http://localh

  7. ruby - Ruby 有像栈、队列、链表、映射或集合这样的容器吗？ - 2

    我在网上查了几个Ruby教程，他们似乎什么都用数组。那么如何在Ruby中实现以下数据结构呢？堆栈队列链表map组 最佳答案 (从评论中移出)好吧，通过限制堆栈或队列方法(push、pop、shift、unshift)，数组可以是堆栈或队列。使用push/pop提供LIFO(后进先出)行为(堆栈)，而使用push/shift或unshift/pop提供FIFO行为(队列)。map是hashes,和一个Set类已经存在。您可以使用类实现链表，但数组将使用标准数组方法提供类似于链表的行为。 关

  8. javascript - 自动展开产品类别树 - 2

    我被困在这个问题上，基本上我需要的是一种自动扩展包含已选中子类别节点的类别树节点的方法。代码中的入口点是js/extjs/ext-tree-checkbox.js和'catalog/category/tree.phtml'可以使用expand()js方法展开节点，展开所有节点并不困难，但这会大大降低页面速度。更新:我测试了以下解决方案:更改js/extjs/ext-tree-checkbox.js渲染方法添加:vartree=n.getOwnerTree();if(tree){expandNodeIds=tree.expandNodeIds.split(',');for(iinexpa

  9. javascript - Vue.js:折叠/展开来自父级的所有元素 - 2

    我需要为我的Vue组件(一些可折叠面板)添加“全部展开/折叠”功能。如果用户点击折叠按钮，然后点击某个面板并展开它，然后点击折叠按钮将不执行任何操作，因为watched参数不会改变。那么如何正确实现此功能(按钮必须始终折叠和展开组件)？我准备了一个简单的例子(抱歉格式不好，它在编辑器中看起来不错:()):varcollapsible={template:"#collapsible",props:["collapseAll"],data:function(){return{collapsed:true}},watch:{ collapseAll:function(value){ this

  10. javascript - 为什么 Math.pow(1, NaN) 在 JavaScript 中等于 NaN？ - 2

    在IEEE754-2008节"9.2.1Specialvalues"有提到pow(+1,y)is1foranyy(evenaquietNaN)如果没有阅读整个文档，维基百科给出了shortcut:The2008versionoftheIEEE754standardsaysthatpow(1,qNaN)andpow(qNaN,0)shouldbothreturn1sincetheyreturn1whateverelseisusedinsteadofquietNaN.为什么Math.pow(1,NaN)在JavaScript中是NaN？不符合标准吗？ 最佳答案

随机推荐