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

Example:

Input:?[1,null,2,3]1\2/3Output:?[1,2,3]

Follow up:?Recursive solution is trivial, could you do it iteratively?

方法一：遞歸

思路很簡單，根左右

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/ class Solution {public void preorderTraversal(TreeNode root) {if(root==null) return ;System.out.print(root.val+' ');preorderTraversal(root.left);preorderTraversal(root.right);} }

方法二：迭代

所有用遞歸的題都能用迭代解，遞歸無非是利用系統(tǒng)的函數(shù)棧，如果自己申請數(shù)據(jù)結(jié)構(gòu)來代替函數(shù)棧，也能實(shí)現(xiàn)相同功能。

前序遍歷是根左右，根先加入棧中，再彈出，每次彈出時(shí)，將彈出結(jié)點(diǎn)的右左子樹加入，保證彈出的順序是根左右。

/*** 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) {if(root==null) return null;if(root!=null) {Stack<TreeNode> stack=new Stack<TreeNode>();List<Integer> list=new ArrayList<Integer>();stack.add(root);while (!stack.isEmpty()){root=stack.pop();list.add(root.val);if(root.right!=null) {stack.add(root.right);}if(root.left!=null){stack.add(root.left);}}}return list;} }

?

轉(zhuǎn)載于:https://www.cnblogs.com/shaer/p/10670108.html

總結(jié)

以上是生活随笔為你收集整理的144. Binary Tree Preorder Traversal（非递归实现二叉树的前序遍历）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。