LeetCode144：二叉树的前序遍历

一时失言乱红尘 2021-09-26 23:46 230阅读 0赞

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

> 示例:  
> 输入: \[1,null,2,3\]  
> 1  
> \\  
> 2  
> /  
> 3  
> 输出: \[1,2,3\]  
> 进阶: 递归算法很简单，你可以通过迭代算法完成吗？

解题思路：用栈实现，  
1.打印当前节点  
2.若存在右子树，则右子树入栈  
3.若存在左子树，则指向左子树，否则，栈不空则出栈，栈空则结束

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    class Solution {
        public List<Integer> preorderTraversal(TreeNode root) {
            List<Integer> list = new ArrayList<>();
            if(root==null)
                return list;
            Stack<TreeNode> stack = new Stack<>();
            TreeNode p = root;
            while(p!=null){
                list.add(p.val);
                if(p.right!=null){
                    stack.push(p.right);
                }
                if(p.left!=null){
                    p = p.left;
                }else{
                    if(stack.isEmpty()){
                        break;
                    }else {
                        p = stack.pop();
                    }
                }
            }
            return list;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，230人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode二叉树系列——144.二叉树的前序遍历

一、题目描述： [144. 二叉树的前序遍历][144.] 给你二叉树的根节点 `root` ，返回它节点值的前序遍历。 ![7b8ad92e53fa48e0a1c

青旅半醒/ 2023年09月28日 17:13/ 0 赞/ 53 阅读

相关 144. 二叉树的前序遍历【78】

> 难度等级：容易 > 上一篇算法： > > [102. 二叉树的层序遍历【206】][102. _206] > 力扣此题地址： > > [144. 二叉树的前序遍历

秒速五厘米/ 2023年09月26日 21:53/ 0 赞/ 65 阅读

相关 144. 二叉树的前序遍历

题目来源 [144. 二叉树的前序遍历][144.] 题目描述 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_s

我不是女神ヾ/ 2022年12月22日 11:11/ 0 赞/ 127 阅读

相关 144. 二叉树的前序遍历

题目： [144. 二叉树的前序遍历][144.] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10

Bertha 。/ 2022年12月09日 01:59/ 0 赞/ 114 阅读

相关 LeetCode[144] 二叉树的前序遍历（迭代）

> 前言：今天的 LeetCode 上的每日一题，[二叉树的前序遍历][Link 1]，用 C++ 实现题目描述给定一个二叉树，返回它的前序遍历。 ![示例][

淩亂°似流年/ 2022年11月20日 08:19/ 0 赞/ 144 阅读

相关 144. 二叉树的前序遍历

> 给你二叉树的根节点 root ，返回它节点值的前序遍历。![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0

迈不过友情╰/ 2022年10月08日 00:45/ 0 赞/ 119 阅读

相关 letcode 144 二叉树的前序遍历

前言题目：[144. 二叉树的前序遍历][144.] 参考题解：[二叉树的递归遍历-代码随想录][-]、[二叉树的迭代遍历-代码随想录][- 1] --------

墨蓝/ 2022年09月11日 06:19/ 0 赞/ 132 阅读

相关 LeetCode144. 二叉树的前序遍历

给定一个二叉树，返回它的前序遍历。示例: 输入: [1,null,2,3] 1 \ 2 /

柔情只为你懂/ 2022年05月10日 08:03/ 0 赞/ 141 阅读

相关 leetcode:144. 二叉树的前序遍历(java)

package LeetCode; import java.util.ArrayList; import java.util.List;

悠悠/ 2021年09月28日 10:22/ 0 赞/ 212 阅读

相关 LeetCode144：二叉树的前序遍历

给定一个二叉树，返回它的前序遍历。 > 示例: > 输入: \[1,null,2,3\] > 1 > \\ > 2 > / > 3 > 输出:

一时失言乱红尘/ 2021年09月26日 23:46/ 0 赞/ 231 阅读