首页 > 代码库 > [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    /   3

 

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

 

Solution 1: 非递归

 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 List<Integer> preorderTraversal(TreeNode root) {12         List<Integer> result=new ArrayList<Integer>();   13         if(root==null){14             return result;15         }16         Stack<TreeNode> s=new Stack<TreeNode>();17         result.add(root.val);18         s.add(root);19         TreeNode p=root.left;20         21         while(!s.isEmpty()){22             while(p!=null){23                 s.add(p);24                 result.add(p.val);25                 p=p.left;26             }27             TreeNode n=s.pop();28             p=n.right;29             if(p!=null){30                 s.add(p);31                 result.add(p.val);32                 p=p.left;33             }34         }35         return result;36     }37 }

 

Solution 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     public List<Integer> preorderTraversal(TreeNode root) {12         List<Integer> result=new ArrayList<Integer>();13         myPreorderTraversal(root,result);14         return result;15     }16 17     private void myPreorderTraversal(TreeNode root, List<Integer> result) {18         // TODO Auto-generated method stub19         if(root!=null){20             result.add(root.val);21             myPreorderTraversal(root.left, result);22             myPreorderTraversal(root.right, result);23         }24     }25 }

 

[Leetcode] Binary Tree Preorder Traversal