首页 > 代码库 > LeetCode: Binary Tree Preorder Traversal 解题报告
LeetCode: 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?
SOLUTION1&2:
递归及非递归解法:
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 // sol1:12 public List<Integer> preorderTraversal1(TreeNode root) {13 List<Integer> ret = new ArrayList<Integer>();14 15 rec(root, ret);16 return ret;17 }18 19 public void rec(TreeNode root, List<Integer> ret) {20 if (root == null) {21 return;22 }23 24 ret.add(root.val);25 rec(root.left, ret);26 rec(root.right, ret);27 }28 29 public List<Integer> preorderTraversal(TreeNode root) {30 List<Integer> ret = new ArrayList<Integer>();31 32 if (root == null) {33 return ret;34 } 35 36 Stack<TreeNode> s = new Stack<TreeNode>();37 s.push(root);38 39 while (!s.isEmpty()) {40 TreeNode cur = s.pop();41 ret.add(cur.val);42 43 if (cur.right != null) {44 s.push(cur.right);45 }46 47 if (cur.left != null) {48 s.push(cur.left);49 }50 }51 52 return ret;53 }54 }
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/tree/PreorderTraversal.java
LeetCode: Binary Tree Preorder Traversal 解题报告
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。