144. Binary Tree Preorder Traversal （二叉树的先序遍历）

桃扇骨 2022-07-14 06:29 51阅读 0赞

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?

题目大意：先序遍历二叉树。

解题思路：

解法一：递归。代码如下：（1ms，beats 28.88%）

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?

解法二：循环。代码如下：（1ms，beats 28.88%）

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        
    	public List<Integer> preorderTraversal(TreeNode root) {
    		List<Integer> list = new ArrayList<>();
    		if(root ==null)
    			return list;
    		TreeNode[] stack = new TreeNode[1000];
    		int index=-1;
    		while(root!=null || index>=0){
    			if(root!=null){
    				list.add(root.val);
    				stack[++index] = root;
    				root = root.left;
    			}else{
    				root = stack[index--].right;
    			}
    		}
    		return list;
    	}
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode：144.Binary Tree PreOrder Traversal（二叉树前序遍历）

> 文章最前：我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如

太过爱你忘了你带给我的痛/ 2022年12月11日 12:18/ 0 赞/ 123 阅读

相关 Leetcode: Binary Tree Preorder Traversal（二叉树前序遍历）

题目： Given a binary tree, return the preorder traversal of its nodes’ values. For exam

忘是亡心i/ 2022年08月07日 10:55/ 0 赞/ 6 阅读

相关 144. Binary Tree Preorder Traversal （二叉树的先序遍历）

Given a binary tree, return the preorder traversal of its nodes' values. For example:

桃扇骨/ 2022年07月14日 06:29/ 0 赞/ 52 阅读

相关 [leetcode-二叉树先序遍历]--144.Binary Tree Preorder Traversal

Question 144. Binary Tree Preorder Traversal > Given a binary tree, return the preorder

喜欢ヅ旅行/ 2022年07月12日 03:27/ 0 赞/ 124 阅读

相关 [Leetcode][python]Binary Tree Preorder Traversal/二叉树的前序遍历

题目大意二叉树前序遍历挑战：迭代解题解题思路递归简单迭代思路：见下方代码前　　1 　　　　　　　/ \

港控/mmm°/ 2022年06月11日 08:17/ 0 赞/ 138 阅读

相关 leetcode 144. Binary Tree Preorder Traversal 二叉树前序遍历 + 深度优先遍历DFS

Given a binary tree, return the preorder traversal of its nodes’ values. For example:

谁借莪１个温暖的怀抱￠/ 2022年06月08日 04:58/ 0 赞/ 176 阅读

相关 LeetCode 144.Binary Tree Preorder Traversal (二叉树的前序遍历)

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

妖狐艹你老母/ 2022年05月08日 13:33/ 0 赞/ 167 阅读

相关 144. Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes' values. Example:

蔚落/ 2022年05月04日 01:28/ 0 赞/ 151 阅读

相关 144. Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes' values. Example:

短命女/ 2022年03月07日 03:46/ 0 赞/ 176 阅读

相关 144. Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes' values. Example:

短命女/ 2022年03月07日 03:44/ 0 赞/ 160 阅读