问题描述:
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?
原问题链接:https://leetcode.com/problems/binary-tree-preorder-traversal/
问题分析
在之前的文章中我有讨论过二叉树的各种遍历方法。对于二叉树的前序遍历序列,我们可以从递归和非递归的两种方式来讨论。
递归解法
这种方法很简单,我们只需要记住递归调用的顺序是当前节点->左子节点->右子节点就可以了。为了记录所有访问的顺序,我们定义一个列表作为参数传进去。
详细的代码实现如下:
/** * 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> result = new LinkedList<>(); if(root == null) return result; preorderTraversal(root, result); return result; } private void preorderTraversal(TreeNode root, List<Integer> list) { if(root == null) return; list.add(root.val); if(root.left != null) preorderTraversal(root.left, list); if(root.right != null) preorderTraversal(root.right, list); } }
非递归解法
二叉树前序遍历的非递归解法有一个比较简单的实现,就是使用一个栈。先将根节点加入到栈中。每次从栈中间弹出顶端的元素。并先后将栈顶元素的右子节点和左子节点压入栈中。这么循环一直到栈为空。需要注意压入栈中的元素顺序。
详细的代码实现如下:
/** * 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> result = new LinkedList<>(); LinkedList<TreeNode> stack = new LinkedList<>(); if(root != null) { stack.push(root); while(!stack.isEmpty()) { TreeNode node = stack.pop(); result.add(node.val); if(node.right != null) stack.push(node.right); if(node.left != null) stack.push(node.left); } } return result; } }
相关推荐
144.Binary_Tree_Preorder_Traversal二叉树的前序遍历【LeetCode单题讲解系列】
leetcode 530 力扣在线评委 # 问题 困难 解决方案 1 简单的 2 中等的 3 中等的 12 中等的 22 中等的 39 中等的 94 中等的 108 中等的 122 中等的 136 中等的 144 中等的 167 中等的 238 中等的 260 中等的 268 中等...
LeetCodeLeetCode solutions(Java)树Minimum Depth of Binary Tree栈evaluate-reverse-polish-notation穷举max-points-on-a-line链表sort-list排序insertion-sort-list树binary-tree-postorder-traversal树binary-...
144-Binary Tree Preorder Traversal94-Binary Tree Inorder Traversal145-Binary Tree Postorder Traversal(后续的非递归时间不够可以先跳过,有点难)层次遍历,队列辅助,相当于广搜。102-Binary Tree Level ...
105.construct_binary_tree_from_preorder_and_inorder_traversal从前序
lru cache leetcode leetcode 记录自己刷leetcode时遇到的一些值得记下来的...binary-tree-preorder-traversal n-queens-ii populating-next-right-pointers-in-each-node sum-root-to-leaf-numbers best-time-to-buy
2sum leetcode 轮廓 1_count_and_say.cpp - super_ugly_number.cpp ...invert_Binary_Tree.cpp - 对称树.cpp - BST_Or_Not.cpp - level_order_traversal.cpp - exponentiation_by_squaring.cpp - Maximum_Depth_B
LeetCode笔记本docsifyjsLeetCode算法Java c / c ++ javascript的基本知识简单的1. Two Sum 704. Classical Binary Search2. 3 Sum206. Reverse Linked List中等的... Binary Tree Preorder Traversal145. Binary Tree
Construct Binary Tree from Preorder and Inorder Traversal Construct Binary Tree from Inorder and Postorder Traversal 二叉查找树 Unique Binary Search Trees Unique Binary Search Trees II Validate Binary...
* [Binary Search Tree](https://github.com/kamyu104/LeetCode#binary-search-tree) * [Breadth-First Search](https://github.com/kamyu104/LeetCode#breadth-first-search) * [Depth-First Search]...
102 Binary Tree Level Order Traversal.js(二叉树级订单Traversal.js) 103 Binary Tree Zigzag Level Order Traversal.js(二叉树之字形级别顺序Traversal.js) 104 Binary Tree.js的最大深度 105从Preorder和...
105.construct-binary-tree-from-preorder-and-inorder-traversal (从前序与中序遍历序列构造二叉树) 106.construct-binary-tree-from-inorder-and-postorder-traversal (从中序与后序遍历序列构造二叉树) 112.path-...
[105_construct-binary-tree-from-preorder-and-inorder-traversal.cpp] [106_construct-binary-tree-from-inorder-and-postorder-traversal.cpp] [107_binary-tree-level-order-traversal-ii.cpp] [108_convert-...
binary-tree-preorder-traversal 链表 linked-list-cycle-ii 链表 linked-list-cycle 链表 copy-list-with-random-pointer 复杂度 single-number 动态规划 candy 贪心 gas-station 动态规划 palindrome-partitioning...
Tree From Preorder Traversal Hard (73.62 %) [1027] Longest Arithmetic Sequence Medium (41.26 %) [1026] Maximum Difference Between Node and Ancestor Medium (55.48 %) [1025] Divisor Game Easy (58.58 %) ...
construct-binary-tree-from-preorder-and-inorder-traversal 无官方题解 106 construct-binary-tree-from-inorder-and-postorder-traversal 无官方题解 116 populating-next-right-pointers-in-eac
Binary Tree from Preorder and Inorder Traversal 用两个栈实现队列 232. Implement Queue using Stacks 旋转数组的最小数字 153. Find Minimum in Rotated Sorted Array 斐波那契数列 509. Fibonacci Number 跳...
java lru leetcode ...Tree/BinaryTree BST HashTable Disjoint Set Trie BloomFilter LRU Cache Algorithm General Coding InOrder/PreOrder/PostOrder Traversal Greedy Recursion/Backtrace Breadth-fi
poj与leetcode 自述文件 介绍 本repo由鞠承佑、钟恺健、王少泽创建。 它在帐户SuanFaRuoji(算法弱鸡)下...└──889_construct_binary_tree_from_preorder_and_postorder_traversal └──zkj_python.py 我们的任务