首页 > 代码库 > Leetcode: Binary Tree Preorder Traversal
Leetcode: Binary Tree Preorder Traversal
Given a binary tree, return the preorder traversal of its nodes‘ values.For example:Given binary tree {1,#,2,3}, 1 2 / 3return [1,2,3].Note: Recursive solution is trivial, could you do it iteratively?
Analysis: 第一反应肯定是recursion(递归), 非常直接，但是题目要求不能用递归。如果要使用迭代的方法来写preorder traversal，最大的问题是要如何确定遍历节点的顺序，因为树的pre-order traversal其实很类似图的DFS，DFS可以用Stack来写，所以这里写pre-order traversal也可以用stack来实现迭代的写法。
iterative:
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */10 public class Solution {11 public ArrayList<Integer> preorderTraversal(TreeNode root) {12 ArrayList<Integer> result = new ArrayList<Integer>();13 Stack<TreeNode> store = new Stack<TreeNode>();14 if (root == null) return result;15 store.push(root);16 while (!store.empty()) {17 TreeNode temp = store.pop();18 result.add(temp.val);19 if (temp.right != null) store.push(temp.right);20 if (temp.left != null) store.push(temp.left);21 }22 return result;23 }24 }
recursion:
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */10 public class Solution {11 public ArrayList<Integer> preorderTraversal(TreeNode root) {12 ArrayList<Integer> result = new ArrayList<Integer>();13 preorder(root, result);14 return result;15 }16 17 public void preorder(TreeNode root, ArrayList<Integer> result) {18 if (root == null) return;19 result.add(root.val);20 preorder(root.left, result);21 preorder(root.right, result);22 }23 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。