首页 > 代码库 > *Binary Tree Preorder Traversal
*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 / 3
return [1,2,3].
Note: Recursive solution is trivial, could you do it iteratively?
代码：深度优先这几个算法思路类似
1 /** 2 * 本代码由九章算法编辑提供。没有版权欢迎转发。 3 * - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。 4 * - 现有的面试培训课程包括：九章算法班，系统设计班，BAT国内班 5 * - 更多详情请见官方网站：http://www.jiuzhang.com/ 6 */ 7 8 Version 0: Non-Recursion (Recommend) 9 /**10 * Definition for binary tree11 * public class TreeNode {12 * int val;13 * TreeNode left;14 * TreeNode right;15 * TreeNode(int x) { val = x; }16 * }17 */18 public class Solution {19 public List<Integer> preorderTraversal(TreeNode root) {20 Stack<TreeNode> stack = new Stack<TreeNode>();21 List<Integer> preorder = new ArrayList<Integer>();22 23 if (root == null) {24 return preorder;25 }26 27 stack.push(root);28 while (!stack.empty()) {29 TreeNode node = stack.pop();30 preorder.add(node.val);31 if (node.right != null) {32 stack.push(node.right);33 }34 if (node.left != null) {35 stack.push(node.left);36 }37 }38 39 return preorder;40 }41 }42 43 //Version 1: Traverse44 public class Solution {45 public ArrayList<Integer> preorderTraversal(TreeNode root) {46 ArrayList<Integer> result = new ArrayList<Integer>();47 traverse(root, result);48 return result;49 }50 // 把root为跟的preorder加入result里面51 private void traverse(TreeNode root, ArrayList<Integer> result) {52 if (root == null) {53 return;54 }55 56 result.add(root.val);57 traverse(root.left, result);58 traverse(root.right, result);59 }60 }61 62 //Version 2: Divide & Conquer63 public class Solution {64 public ArrayList<Integer> preorderTraversal(TreeNode root) {65 ArrayList<Integer> result = new ArrayList<Integer>();66 // null or leaf67 if (root == null) {68 return result;69 }70 71 // Divide72 ArrayList<Integer> left = preorderTraversal(root.left);73 ArrayList<Integer> right = preorderTraversal(root.right);74 75 // Conquer76 result.add(root.val);77 result.addAll(left);78 result.addAll(right);79 return result;80 }81 }
自己的解法： Non-Recursion (Recommend)
1 public class Solution { 2 public List<Integer> preorderTraversal(TreeNode root) 3 { 4 List<Integer> result = new ArrayList<Integer> (); 5 LinkedList<TreeNode> stack = new LinkedList<TreeNode>(); 6 7 while(root!=null||stack.isEmpty()==false) 8 { 9 if(root!=null)10 {11 result.add(root.val);12 stack.push(root);13 root=root.left;14 }15 else16 {17 root=stack.pop();18 root=root.right;19 20 }21 }22 23 return result;24 }25 }
*Binary Tree Preorder Traversal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。