144. Binary Tree Preorder Traversal（非递归实现二叉树的前序遍历）

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);} }

方法二：迭代

所有用递归的题都能用迭代解，递归无非是利用系统的函数栈，如果自己申请数据结构来代替函数栈，也能实现相同功能。

前序遍历是根左右，根先加入栈中，再弹出，每次弹出时，将弹出结点的右左子树加入，保证弹出的顺序是根左右。

/*** 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;} }

 

转载于:https://www.cnblogs.com/shaer/p/10670108.html

总结

以上是生活随笔为你收集整理的144. Binary Tree Preorder Traversal（非递归实现二叉树的前序遍历）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。