首页 > 代码库 > 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 }
View Code

 

https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/tree/PreorderTraversal.java

LeetCode: Binary Tree Preorder Traversal 解题报告