1. 首页
  2. LeetCode 刷题网

LeetCode 144. 二叉树的前序遍历

题目描述

给定一个二叉树,返回它的 前序 遍历。

 示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,2,3]
进阶: 递归算法很简单,你可以通过迭代算法完成吗?

难度:Middle

前置知识

  • 递归

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

这道题目是前序遍历,这个和之前的leetcode 94 号问题 - 中序遍历完全不一回事。

前序遍历是根左右的顺序,注意是开始,那么就很简单。直接先将根节点入栈,然后
看有没有右节点,有则入栈,再看有没有左节点,有则入栈。 然后出栈一个元素,重复即可。

其他树的非递归遍历可没这么简单

LeetCode 144. 二叉树的前序遍历

(迭代 VS 递归)

关键点解析

  • 二叉树的基本操作(遍历)
    > 不同的遍历算法差异还是蛮大的
  • 如果非递归的话利用栈来简化操作

  • 如果数据规模不大的话,建议使用递归

  • 递归的问题需要注意两点,一个是终止条件,一个如何缩小规模

  1. 终止条件,自然是当前这个元素是 null(链表也是一样)

  2. 由于二叉树本身就是一个递归结构, 每次处理一个子树其实就是缩小了规模,
    难点在于如何合并结果,这里的合并结果其实就是mid.concat(left).concat(right),
    mid 是一个具体的节点,left 和 right递归求出即可

代码

  • 语言支持:JS,C++

JavaScript Code:

/**
 * @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍:是以前端进阶资源教程分享为主的专业网站,包括:前端、大厂面试题、typescript教程、程序人生、React.js
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
  // 1. Recursive solution

  // if (!root) return [];

  // return [root.val].concat(preorderTraversal(root.left)).concat(preorderTraversal(root.right));

  // 2. iterative solutuon

  if (!root) return [];
  const ret = [];
  const stack = [root];
  let t = stack.pop();

  while (t) {
    if (t.right) {
      stack.push(t.right);
    }
    if (t.left) {
      stack.push(t.left);
    }
    ret.push(t.val);
    t = stack.pop();
  }

  return ret;
};

C++ Code:

/**
 * @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍:是以前端进阶资源教程分享为主的专业网站,包括:前端、大厂面试题、typescript教程、程序人生、React.js
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> v;
        vector<TreeNode*> s;
        while (root != NULL || !s.empty()) {
            while (root != NULL) {
                v.push_back(root->val);
                s.push_back(root);
                root = root->left;
            }
            root = s.back()->right;
            s.pop_back();
        }
        return v;
    }
};

复杂度分析

  • 时间复杂度:$O(N)$
  • 空间复杂度:$O(N)$

相关专题

更多题解可以访问我的 JS中文网 – 码农周刊 仓库:https://github.com/meibin08/free-programming-books, 一起学习更多前端前沿知识。

看完两件小事

如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:

  1. 关注我们的 GitHub 博客,让我们成为长期关系
  2. 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
  3. 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程

JS中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。欢迎热爱技术的你一起加入交流与学习,JS中文网的使命是帮助开发者用代码改变世界

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com

标题:LeetCode 144. 二叉树的前序遍历

链接:https://www.javascriptc.com/4508.html

« 基于Koa2打造属于自己的MVC框架,仿egg的简易版本
LeetCode 143. 重排链表»
Flutter 中文教程资源

相关推荐

QR code