首页 > 试题广场 >

求二叉树的前序遍历

[编程题]求二叉树的前序遍历
  • 热度指数：52672 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
求给定的二叉树的前序遍历。
例如：
给定的二叉树为{1,#,2,3},
返回：[1,2,3].
备注；用递归来解这道题很简单，你可以给出迭代的解法么？
如果你不明白{1,#,2,3}的含义，点击查看相关信息
示例1

输入

{1,#,2,3}

输出

[1,2,3]

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
Java
特不靠谱头像 特不靠谱
从高到底，从左到右的排查方式，即可用递归方式排查。
采用递归方式排查 ：
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     *
     * @param root TreeNode类
     * @return int整型ArrayList
     */

    ArrayList<Integer> vals = new ArrayList<>();
    public ArrayList<Integer> preorderTraversal (TreeNode root) {
        // write code here
        // ArrayList<Integer> vals = new ArrayList<>();
        if (root == null) {
            return vals;
        }
        getVal(root);

        return vals;
    }

    public void getVal(TreeNode node) {
        vals.add(node.val);
        if (node.left != null) {
            getVal(node.left);
        }
        if(node.right != null){
            getVal(node.right);
        }
    }
}


发表于 2023-03-29 17:34:48 回复(0)
Java
牛客267940113号头像 牛客267940113号
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型ArrayList
     */
public ArrayList<Integer> preorderTraversal (TreeNode root) {
    ArrayList<Integer> result = new ArrayList();
    if(root == null){
        return result; 
    }
    result.add(root.val);
    
    TreeNode left = root.left;
    TreeNode right = root.right;

    if(left != null){
        result.addAll(preorderTraversal(left));
    }
    if(right != null){
        result.addAll(preorderTraversal(right));
    }
    
    return result;    
}
}

发表于 2022-04-26 00:40:57 回复(0)
Java
裤兜里的纸巾头像 裤兜里的纸巾 
public class Solution {

   public ArrayList<Integer> preorderTraversal (TreeNode root) {
        // write code here
        ArrayList<Integer> list = new ArrayList<>();
        if (root == null) return list;
        LinkedList<TreeNode> treeNodes = new LinkedList<>();
        TreeNode prev = null;
        while(root!=null || !treeNodes.isEmpty()){
            //将左节点进栈
            while (root!= null){
                treeNodes.push(root);
                list.add(root.val);
                root = root.left;
            }
            root = treeNodes.pop();
            if (root.right ==null ||  root.right == prev){
                prev = root;
                root = null;
            }else {
                root = root.right;
            }
        }
        return list;
    }
}

发表于 2021-11-30 16:33:37 回复(0)
Java
andy爱学习爱分享头像 andy爱学习爱分享
这道题真是垃圾啊，必须要返回一个空list，返回null直接报错，题目也没有给出传null的时候返回什么。还有题目中的#我也是服了，你把#换成null不行吗？ 

    public ArrayList<Integer> preorderTraversal (TreeNode root) {
        if(root==null){
            return null;
        }
        ArrayList<Integer> result=new ArrayList();
        // write code here
        Stack<TreeNode>  stack=new Stack();
        stack.push(root);
        while(!stack.empty()){
            TreeNode pop=stack.pop();
            result.add(pop.val);                
            TreeNode right=pop.right;
            if(right!=null){
                stack.push(right);
            }        
            TreeNode left=pop.left;
            if(left!=null){
                stack.push(left);
            }
        }
        return result;
    }


发表于 2021-10-21 00:56:33 回复(0)
Java
岛。201904182324772头像 岛。201904182324772
public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型ArrayList
     */
    public ArrayList<Integer> preorderTraversal (TreeNode root) {
        ArrayList<Integer> res=new ArrayList<>();
        preOrder(root,res);
        return res;
        // write code here
    }
    public void preOrder(TreeNode root,ArrayList<Integer> res){
        if(root==null) return;
        res.add(root.val);
        preOrder(root.left,res);
        preOrder(root.right,res);
    }
}
发表于 2021-09-08 21:18:24 回复(0)
Java
会飞的包子123头像 会飞的包子123
public ArrayList<Integer> preorderTraversal (TreeNode root) {
        // write code here
        //前序遍历：根左右
        Stack<TreeNode> stack=new Stack<TreeNode>();
        ArrayList<Integer> list=new ArrayList<Integer>();
        if(root!=null){
            stack.push(root);
            while(stack!=null && stack.size()!=0){
                TreeNode p=stack.pop();
                list.add(p.val);
                if(p.right!=null){
                    stack.push(p.right);
                }
                if(p.left!=null){
                    stack.push(p.left);
                }
            }
            
        }
        return list;
        
    }
发表于 2021-08-08 00:40:59 回复(0)
Java
波文头像 波文 
import java.util.ArrayList;
import java.util.List;

/**
 * @program: arask
 * @description: 编程测试
 * @author: fubowen
 * @create: 2020-10-10 15:21
 **/
public class Solution {
    /**
     *
     * @param root TreeNode类
     * @return int整型ArrayList
     */
    public ArrayList<Integer> preorderTraversal (TreeNode root) {
        // write code here
        //root为空 不为空
        //先根  左子树 右子树
        ArrayList<Integer> list=new ArrayList<>();
        if(root!=null){
            list.add(root.val);
           ArrayList<Integer> leftList=preorderTraversal(root.left);
           list.addAll(leftList);
           ArrayList<Integer> rightList=preorderTraversal(root.right);
           list.addAll(rightList);
        }
        return list;
    }
}

编辑于 2020-10-12 11:24:24 回复(0)
Java
青椒肉丝头像 青椒肉丝 
import java.util.*;
public class Solution {
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
        //后进先出栈
        ArrayList<Integer> al = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        if(root!=null){
            stack.push(root);
            while(!stack.isEmpty()){
                //1、根
                TreeNode tmp = stack.pop();
                al.add(tmp.val);
                //2、先入后出，右边子树在后
                if(tmp.right!=null){
                    stack.push(tmp.right);
                }
                //2、**先出，左边子树在前
                if(tmp.left!=null){
                    stack.push(tmp.left);
                }
            }
            
        }
        return al;
        
    }
}

发表于 2020-04-22 22:56:57 回复(0)
Java
追梦赤子心2019头像 追梦赤子心2019
这里考察的是使用栈来前序遍历二叉树 
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        ArrayList<Integer> list = new ArrayList<Integer>();
        if(root != null){
            stack.push(root);
        }
        while(stack.size() > 0){
            if(stack.peek() != null){
                list.add(stack.peek().val);
                stack.push(stack.peek().left);
            }else{
                stack.pop();
                if(stack.size() > 0 && stack.peek() != null){
                    stack.push(stack.pop().right);
                }
            }
            
        }
        return list;
        
    }
}


发表于 2020-04-21 10:02:31 回复(0)
Java
牛客772486546号头像 牛客772486546号
/**
 * 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<Integer> res = new ArrayList<Integer>();
        Stack<TreeNode> s = new Stack<TreeNode>();
        TreeNode p = root;
        s.push(p);
        while(!s.isEmpty()){
            p = s.pop();
            res.add(p.val);
            if(p.right!=null)
                s.push(p.right);
            if(p.left!=null)
                s.push(p.left);
        }
        return res;
    }
}
发表于 2020-03-14 17:15:00 回复(0)
Java
I_Mars头像 I_Mars 
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> list=new ArrayList<Integer>();
        if(root==null)
            return list;
        function(list,root);
        return list;
    }
    public void function(ArrayList<Integer> list,TreeNode root){
        if(root==null)
            return;
        list.add(root.val);
        if(root.left!=null){
            function(list,root.left);
        }
        if(root.right!=null){
            function(list,root.right);
        }
        
    }
}

发表于 2020-02-21 14:46:56 回复(0)
Java
AriesLi头像 AriesLi 
import java.util.*;

public class Solution {
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        if(root==null) return list;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            list.add(node.val);
            if(node.right!=null) stack.push(node.right);
            if(node.left!=null) stack.push(node.left);
        }
        return list;
    }
}

发表于 2019-12-30 14:51:35 回复(0)
Java
Krow头像 Krow 
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;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while(!stack.isEmpty()){
            root = stack.pop();
            list.add(root.val);
            if(root.right != null)
                stack.push(root.right);
            if(root.left != null)
                stack.push(root.left);
        }
        return list;
    }
}
利用栈的思想，后进先出
发表于 2019-08-22 14:12:58 回复(0)
Java
我去个地方啊头像 我去个地方啊

题目描述

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?

解题思路

同上题，只需要稍微换一下位置即可，十分方便。

代码提交

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)
Java
放学后我不走~头像 放学后我不走~
先把根点的值加入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)
Java
Sakula头像 Sakula
import java.util.*;

public class Solution {
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
        ArrayList res = new ArrayList<>();
        if (root == null) return res;
        // 先添加根节点值
        res.add(root.val);
        // 如果当前节点为叶子节点
        if (root.left == null && root.right == null) {
            return res;
        }
        // 如果左儿子存在
        if (root.left != null) {
            res.addAll(preorderTraversal(root.left));
        }
        // 如果右儿子存在
        if (root.right != null) {
            res.addAll(preorderTraversal(root.right));
        }
        return res;
    }
}

发表于 2018-06-29 13:12:57 回复(0)
Java
中本聪007头像 中本聪007 
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)
Java
随心思念～头像 随心思念～
import java.util.ArrayList;
import java.util.Stack;
//若有左子树则一直先遍历左子树，若左子树为空则遍历右子树
//重复以上步骤直到栈为空。
public class Solution {
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        if(root == null) return list;
        Stack<TreeNode> s = new Stack<TreeNode>();
        TreeNode p = root;
        while(!s.isEmpty() || p != null){
            if(p !=null){
                list.add(p.val);
                s.push(p);
                p = p.left;
            }
            else{
                p = s.peek().right;
                s.pop();
            }
        }
        return list;
    }
}

发表于 2018-05-08 10:40:03 回复(0)
提交观点

问题信息

栈 树
难度：
32条回答 35344浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号