LeetCode 144. Binary Tree Preorder Traversal

发布于: 2020 年 07 月 19 日
LeetCode 144. Binary Tree Preorder Traversal

问题描述

给定一颗二叉树,以先序遍历的顺序返回其节点。

栗子:

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

最后,题主还附加了一句:使用递归没啥,你能够用遍历的方式完成吗?

想看英文原文的戳这里

解题思路

首先,介绍一下先序遍历。

始终是先遍历根节点,再遍历左节点,最后遍历右节点。对于子树也一样。

递归

使用递归的方式是最简单的,按根节点 -> 左节点 -> 右节点的顺序即可。

由于题目要求返回遍历的节点,因此将节点存入数组就好。

直接上代码:

var preorderTraversal = function (root) {
let result = [];
preoderTraversalRecursive(root, result);
return result;
};
var preoderTraversalRecursive = function (root, result) {
if (root) {
// 根节点
result.push(root.val);
// 左节点
preoderTraversalRecursive(root.left, result);
// 右节点
preoderTraversalRecursive(root.right, result);
}
};

遍历

如果以遍历的方式,稍微复杂一丢丢,但是实现起来也不困难。

主要是利用栈的思想,先进后出。由于左节点要先于右节点遍历,因此将右节点先进栈,左节点后进栈。

该实现的 js 代码如下:

var preoderTraversalIterative = function (root) {
let result = [];
if (root) {
let list = [];
list.push(root);
while (list.length > 0) {
// 取第一个数据
const node = list.shift();
result.push(node.val);
// 右节点进栈
if (node.right) {
list.unshift(node.right);
}
// 左节点进栈
if (node.left) {
list.unshift(node.left);
}
}
}
return result;
};

发布于: 2020 年 07 月 19 日 阅读数: 4
用户头像

liu_liu

关注

不要相信自己的记忆力 2017.11.13 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode 144. Binary Tree Preorder Traversal