求给定的二叉树的前序遍历。
例如：
给定的二叉树为{1,#,2,3},
返回：[1,2,3].
备注；用递归来解这道题很简单，你可以给出迭代的解法么？
如果你不明白{1,#,2,3}的含义，点击查看相关信息
[编程题]求二叉树的前序遍历
//栈实现先序遍历
vector<int> preorderTraversal(TreeNode *root) {
vector<int> preorder;
stack<TreeNode*> st;
TreeNode *p=root;
while(p||!st.empty()){
if(p){
preorder.push_back(p->val);
st.push(p);
p=p->left;
}
else{
p=st.top();
st.pop();
p=p->right;
}
}
return preorder;
}
发表于 2016-08-15 20:42:50
回复(0)
import java.util.ArrayList;
import java.util.Stack;
// 使用栈的思想来模拟递归
public class Solution {
public ArrayList<Integer> preorderTraversal(TreeNode root) {
if (root == null) {
return new ArrayList<Integer>();
}
ArrayList<Integer> result = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.add(root);
while (!stack.isEmpty()) {
TreeNode tmp = stack.pop();
result.add(tmp.val);
if (tmp.right != null) {
stack.add(tmp.right);
}
if (tmp.left != null) {
stack.add(tmp.left);
}
}
return result;
}
}
发表于 2018-09-06 15:28:11
回复(0)
import java.util.*;
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public ArrayList<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> ret = new ArrayList<>();
if (root == null) {
return ret;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
ret.add(node.val);
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
return ret;
}
}
发表于 2017-04-03 21:30:32
回复(0)
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
#
#
# @param root TreeNode类
# @return int整型一维数组
#
class Solution:
def preorderTraversal(self , root ):
# write code here
reList = []
if root is None:
return reList
stack = []
node = root
while node is not None:
if isinstance(node.val, int):
reList.append(node.val)
if node.right is not None:
stack.append(node.right)
node = node.left
if node is None and len(stack)>0:
node = stack.pop(-1)
return reList
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
#
#
# @param root TreeNode类
# @return int整型一维数组
#
class Solution:
def preorderTraversal(self , root ):
# write code here
reList = []
if root is None:
return reList
stack = []
node = root
while node is not None:
if isinstance(node.val, int):
reList.append(node.val)
if node.right is not None:
stack.append(node.right)
node = node.left
if node is None and len(stack)>0:
node = stack.pop(-1)
return reList
前序遍历的迭代算法关键在于：设置一个栈，每次将节点的右孩子压入栈中，当遍历完根节点和左子树，便从栈中弹出右子树，继续循环深入
发表于 2020-08-21 12:39:05
回复(0)
class Solution {
public:
vector<int> ans;
vector<int> preorderTraversal(TreeNode *root) {
if (root == NULL) return ans;
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
TreeNode *top = st.top(); st.pop();
ans.push_back(top->val);
if (top->right != NULL) {
st.push(top->right);
}
if (top->left != NULL) {
st.push(top->left);
}
}
return ans;
}
};
发表于 2020-07-11 14:14:55
回复(0)
创建一个保存二叉树的ArrayList,
根据数组长度判断历遍是否完成,
每次取数组末尾,将末尾的值添加到保存结果的数组中,
再取出末尾的左右子树,
移除掉数组的末尾用他的子树替代他,
因为是前序历遍,
优先添加右子树,
再添加左子树.
循环直到数组长度为0,
输出结果.
/**
* Definition for binary tree* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
import java.util.*;
public class Solution {
public ArrayList<Integer> preorderTraversal(TreeNode root) {
if(root==null)
return new ArrayList<Integer>();
ArrayList<TreeNode> temp= new ArrayList<>();
ArrayList<Integer> res= new ArrayList<>();
temp.add(root);
while(temp.size()!=0){
TreeNode tempTree=temp.get(temp.size()-1);
res.add(tempTree.val);
temp.remove(temp.size()-1);
if(tempTree.right!=null){
temp.add(tempTree.right);
}
if(tempTree.left!=null){
temp.add(tempTree.left);
}
}
return res;
}
}
发表于 2020-03-19 10:51:05
回复(0)
import java.util.Stack;
import java.util.ArrayList;
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public ArrayList<Integer> preorderTraversal(TreeNode root) {
/*递归解，不满足题意
ArrayList<Integer> list = new ArrayList<Integer>();
if(root == null)
return list;
test(root, list);
return list;
}
private void test(TreeNode root, ArrayList<Integer> list)
{
list.add(root.val);
if(root.left != null)
{
test(root.left, list);
}
if(root.right != null)
{
test(root.right, list);
}
}*/
if(root == null)
return list;
else
{
Stack stack = new Stack();
stack.push(root);
while(!stack.isEmpty())
{
root = (TreeNode)stack.pop();
list.add(root.val);
while( root != null)
{
if(root.left != null)
list.add(root.left.val);
if(root.right != null)
stack.push(root.right);
root = root.left;
}
}
}
return list;
}
}
import java.util.ArrayList;
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public ArrayList<Integer> preorderTraversal(TreeNode root) {
/*递归解，不满足题意
ArrayList<Integer> list = new ArrayList<Integer>();
if(root == null)
return list;
test(root, list);
return list;
}
private void test(TreeNode root, ArrayList<Integer> list)
{
list.add(root.val);
if(root.left != null)
{
test(root.left, list);
}
if(root.right != null)
{
test(root.right, list);
}
}*/
//以下为非递归解
//从二叉树的根节点出发，沿该节点的左子树出发向下搜索，每遇到节点就访问，并将该节点的非空右
//孩子节点压栈。左子树访问完成后，从栈顶弹出节点的右孩子节点，然后用同样的方法去遍历右子树
ArrayList<Integer> list = new ArrayList<Integer>();if(root == null)
return list;
else
{
Stack stack = new Stack();
stack.push(root);
while(!stack.isEmpty())
{
root = (TreeNode)stack.pop();
list.add(root.val);
while( root != null)
{
if(root.left != null)
list.add(root.left.val);
if(root.right != null)
stack.push(root.right);
root = root.left;
}
}
}
return list;
}
}
发表于 2020-01-05 18:11:41
回复(0)
/**
* Definition for binary tree
* 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;
if(root==nullptr)
return res;
stack<TreeNode *> stackNode;
TreeNode * leftNode=root;
while(leftNode!=nullptr)
{
res.push_back(leftNode->val);
stackNode.push(leftNode);
leftNode=leftNode->left;
}
while(!stackNode.empty())
{
TreeNode *p=stackNode.top();
stackNode.pop();
if(p->right!=nullptr)
{
TreeNode * q=p->right;
while(q!=nullptr)
{
res.push_back(q->val);
stackNode.push(q);
q=q->left;
}
}
}
return res;
}
};
发表于 2019-08-13 12:52:46
回复(0)
// morris 先序遍历
class Solution {
public:
vector<int> res;
vector<int> preorderTraversal(TreeNode *root) {
TreeNode *cur = root;
while(cur){
if(cur -> left == NULL){
res.push_back(cur -> val);
cur = cur -> right;
}
else{
TreeNode *mostRight = cur -> left;
while(mostRight -> right && mostRight -> right != cur) mostRight = mostRight -> right;
if(mostRight -> right == NULL){
res.push_back(cur -> val);
mostRight -> right = cur;
cur = cur -> left;
}
else{
mostRight -> right = NULL;
cur = cur -> right;
}
}
}
return res;
}
};
class Solution {
public:
vector<int> res;
vector<int> preorderTraversal(TreeNode *root) {
TreeNode *cur = root;
while(cur){
if(cur -> left == NULL){
res.push_back(cur -> val);
cur = cur -> right;
}
else{
TreeNode *mostRight = cur -> left;
while(mostRight -> right && mostRight -> right != cur) mostRight = mostRight -> right;
if(mostRight -> right == NULL){
res.push_back(cur -> val);
mostRight -> right = cur;
cur = cur -> left;
}
else{
mostRight -> right = NULL;
cur = cur -> right;
}
}
}
return res;
}
};
发表于 2019-03-25 15:29:23
回复(0)
题目描述
Given a binary tree, return the preorder traversal of its nodes' values.
For example:
Given binary tree{1,#,2,3},
1
\
2
/
3return[1,2,3].
Note: Recursive solution is trivial, could you do it iteratively?
解题思路
同上题，只需要稍微换一下位置即可，十分方便。
代码提交
import java.util.*;
class Command{
public String str;
public TreeNode node;
public Command(String str,TreeNode node){
this.str = str;
this.node = node;
}
}
public class Solution {
public ArrayList preorderTraversal(TreeNode root) {
ArrayList res = new ArrayList();
if(root == null){
return res;
}
Stack stack = new Stack();
stack.push(new Command("go",root));
while(!stack.isEmpty()){
Command c = stack.pop();
if(c.str == "print"){
res.add(c.node.val);
}else{
if(c.node.right != null){
stack.push(new Command("go",c.node.right));
}
if(c.node.left != null){
stack.push(new Command("go",c.node.left));
}
stack.push(new Command("print",c.node));
}
}
return res;
}
}
编辑于 2019-03-24 19:33:39
回复(0)
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public ArrayList<integer> preorderTraversal(TreeNode root) {
ArrayList<integer> r = new ArrayList<>();
if (root != null) {
Stack<treenode> s = new Stack<>();
TreeNode p = null;
s.push(root);
while (!s.empty()) {
p = s.pop();
r.add(p.val);
if (p.right != null)
s.push(p.right);
if (p.left != null)
s.push(p.left);
}
}
return r;
}
}
编辑于 2019-01-21 11:25:15
回复(0)
先把根点的值加入list，把root.right 压栈，然后root 指向root.left，反复执行，到空时，出栈，再反复执行
import java.util.Stack;
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> list = new ArrayList<Integer>();
Stack<TreeNode> s = new Stack<TreeNode>();
while(root!=null || !s.isEmpty()){
while(root!=null){
s.push(root.right);
list.add(root.val);
root = root.left;
}
root = s.pop();
}
return list;
}
}
发表于 2018-08-31 20:00:33
回复(0)
import java.util.*;
public class Solution {
ArrayList<Integer> arr=new ArrayList<>();
public ArrayList<Integer> preorderTraversal(TreeNode root) {
if(root==null) return arr;
isPre(root);
return arr;
}
public void isPre(TreeNode root){
if(root!=null){
arr.add(root.val);
isPre(root.left);
isPre(root.right);
}
}
}
发表于 2018-08-11 10:23:18
回复(0)
import java.util.Stack;
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> list = new ArrayList<Integer>();
if(root==null){
return list;
}
TreeNode t = root;
Stack<TreeNode> st = new Stack<TreeNode>();
while(t!=null || !st.empty()){
while(t!=null){
list.add(t.val);
st.push(t);
t = t.left;
}
if(!st.empty()){
t = st.pop();
t = t.right;
}
}
return list;
}
}
发表于 2018-07-14 14:18:24
回复(0)
import java.util.*;//还是递归好用
public class Solution {
public ArrayList<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> al = new ArrayList<Integer>();
if(root==null)return al;
al.add(root.val);
al.addAll(preorderTraversal(root.left));
al.addAll(preorderTraversal(root.right));
return al;
}
}
发表于 2018-06-09 16:42:11
回复(0)
/*
* 思路： 可以动手实验一下哦！
* 1.申请1个栈，记为stack,然后将头节点head压入stack中。
* 2.从stack中弹出的节点记为cur，然后记录cur节点的值（或是打印，根据题目需要），再将cur的右孩子节点压入栈中（如果右孩子不为空）
* 最后再将cur的左孩子（如果不为空），压入stack中。
* 3.不断重复，步骤2，直到stack为空，过程停止。
*/
import java.util.ArrayList;
import java.util.Stack;
public class BinaryTreePreOrderTraversal {
public ArrayList<Integer> preorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
ArrayList<Integer> res = new ArrayList<>();
if (root != null) {
stack.push(root);
while(!stack.isEmpty()) {
TreeNode cur = stack.pop();
res.add(cur.val);
if (cur.right != null) {
stack.push(cur.right);
}
if (cur.left != null) {
stack.push(cur.left);
}
}
}
return res;
}
}
发表于 2018-04-26 10:39:20
回复(0)
public ArrayList<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer>list = new ArrayList<Integer>();
if(root == null) return list ;
Stack<TreeNode> s = new Stack <TreeNode>();
s.push(root);
while(!s.empty()){
TreeNode node = s.pop();
list.add(node.val);
if(node.right!=null) s.push(node.right);
if(node.left !=null) s.push(node.left);
}
return list;
}
ArrayList<Integer>list = new ArrayList<Integer>();
if(root == null) return list ;
Stack<TreeNode> s = new Stack <TreeNode>();
s.push(root);
while(!s.empty()){
TreeNode node = s.pop();
list.add(node.val);
if(node.right!=null) s.push(node.right);
if(node.left !=null) s.push(node.left);
}
return list;
}
发表于 2018-04-09 09:13:20
回复(0)
C++ solution:
class Solution {
public:
vector<int> preorderTraversal(TreeNode *root) {
vector<int> result;
helper(root,result);
return result;
}
void helper(TreeNode *node,vector<int> &result){
if (node==NULL){
return;
}
result.push_back(node->val);
helper(node->left,result);
helper(node->right,result);
}
};
编辑于 2017-10-27 17:01:48
回复(0)
package go.jacob.day0527.stackqueue;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
* 给定一个二叉树，返回它的 前序 遍历。
* <p>
* 示例:
* <p>
* 输入: [1,null,2,3]
* 1
* \
* 2
* /
* 3
* <p>
* 输出: [1,2,3]
* 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
* <p>
* 解法：
* 二叉树遍历分为递归和非递归版本（都需要掌握）
* 面试中偏向于问非递归实现
*/
public class P144_BinaryTreePreorderTraversal {
/*
递归实现，代码很简单
*/
public static List<Integer> preorderTraversal_1(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
helper(root, res);
return res;
}
private static void helper(TreeNode root, List<Integer> res) {
if (root == null)
return;
res.add(root.val);
helper(root.left, res);
helper(root.right, res);
}
/*
非递归实现，重点掌握
*/
public static List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if (root == null)
return res;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
res.add(root.val);
TreeNode cur = root.left;
while (!stack.isEmpty() || cur != null) {
if (cur == null) {
cur = stack.pop().right;
continue;
}
res.add(cur.val);
stack.push(cur);
cur = cur.left;
}
return res;
}
}
编辑于 2018-05-27 16:03:33
回复(1)
问题信息
难度：
187条回答
144收藏
35899浏览
通过挑战的用户
查看代码-
2023-02-16 17:36:14
-
2023-02-15 22:54:12 -
2022-10-15 21:30:47
-
2022-10-02 10:39:34
-
2022-09-16 18:55:00
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
