【LeetCode】144. Binary Tree Preorder Traversal 解题报告（Python&C++&Java）
2024-09-07 19:26:37
- 作者： 负雪明烛
- id： fuxuemingzhu
- 个人博客：http://fuxuemingzhu.cn/
题目地址：https://leetcode.com/problems/binary-tree-preorder-traversal/#/description
题目描述
Given a binary tree, return the preorder traversal of its nodes’ values.
For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,2,3].
Note: Recursive solution is trivial, could you do it iteratively?
题目大意
求一个二叉树的先序遍历。
解题方法
递归
递归的思路就是先保存根节点的值，然后递归左子树和右子树。
python代码如下：
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root: return []
res = []
res.append(root.val)
res.extend(self.preorderTraversal(root.left))
res.extend(self.preorderTraversal(root.right))
return res
Java代码如下：
public class Solution {
List<Integer> ans = new ArrayList<Integer>();
public List<Integer> preorderTraversal(TreeNode root) {
preOrder(root);
return ans;
}
public void preOrder(TreeNode root){
if(root == null){
return;
}
ans.add(root.val);
preOrder(root.left);
preOrder(root.right);
}
}
C++代码如下：
/**
* 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> res;
preorder(root, res);
return res;
}
void preorder(TreeNode* root, vector<int>& res) {
if (!root) return;
res.push_back(root->val);
preorder(root->left, res);
preorder(root->right, res);
}
};
迭代
迭代版本的需要使用栈，先把右孩子进栈，再左孩子进栈。
为什么这个访问顺序呢？我们知道栈是后进先出的数据结构，所以遍历完根节点之后，把右孩子放到栈里，把左孩子放到栈里，那么下一次在出栈的时候是左孩子，所以总之就是个根-->左-->右先序遍历的过程了。
Python代码如下：
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root: return []
res = []
stack = []
stack.append(root)
while stack:
node = stack.pop()
if not node:
continue
res.append(node.val)
stack.append(node.right)
stack.append(node.left)
return res
Java代码如下：
public class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
if(root == null){
return new ArrayList<Integer>();
}
List<Integer> ans = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode temp = stack.pop();
ans.add(temp.val);
if(temp.right != null){
stack.push(temp.right);
}
if(temp.left != null){
stack.push(temp.left);
}
}
return ans;
}
}
C++代码如下：
/**
* 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> res;
stack<TreeNode*> s;
s.push(root);
while (!s.empty()) {
auto node = s.top(); s.pop();
if (!node) continue;
res.push_back(node->val);
s.push(node->right);
s.push(node->left);
}
return res;
}
};
日期
2017 年 5 月 20 日
2019 年 1 月 25 日 —— 这学期最后一个工作日
2019 年 9 月 20 日 —— 是选择中国互联网式加班？还是外企式养生？
最新文章
- BootStrap table使用
- 【记录】ASP.NET MVC View 移动版浏览的奇怪问题
- rt—移植笔记1
- UltraEdit 列模式
- maven+jetty项目在tomcat部署
- PHP学习笔记五【方法】
- wemall app商城源码Android数据的SharedPreferences储存方式
- dbcp连接池不合理的锁导致连接耗尽
- Data Lake Analytics + OSS数据文件格式处理大全
- SQL 农经权数据库问题提取_身份证号码相同（字段值出现多次）；身份证号码相同但姓名不同（A字段相同，B字段不相同）；发包方无承包方信息（A表有，B表无）等
- RS232、RS485和RS422
- 一个简单的使用Quartz和Oozie调度作业给大数据计算平台执行
- [洛谷3375]【模板】KMP字符串匹配
- java aop做一个接口耗时的计算
- git查看添加删除远程仓库
- Teamwork（The second day of the team）
- Codeforces Round #307 (Div. 2) C. GukiZ hates Boxes 二分
- WPF TextCompositionManager 事件说明
- 实用爬虫-02-爬虫真正使用代理 ip
- 【EF】EntityFramework DBFirst的使用