2015年10月15日星期四

Leetcode 144 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: recursive DFS
 public class Solution {  
   public List<Integer> preorderTraversal(TreeNode root) {  
     List<Integer> res=new ArrayList<>();  
     dfs(root,res);  
     return res;  
   }  
   private void dfs(TreeNode x, List<Integer> res) {  
     if (x==null) return;  
     res.add(x.val);  
     dfs(x.left, res);  
     dfs(x.right, res);  
   }  
 }  

Solution 2: iterative DFS
 public class Solution {  
   public List<Integer> preorderTraversal(TreeNode root) {  
     Deque<TreeNode> stack=new LinkedList<>();  
     List<Integer> res=new ArrayList<>();  
     TreeNode x=root;  
     while (x!=null || !stack.isEmpty()) {  
       if (x!=null) {  
         res.add(x.val);  
         stack.push(x);  
         x=x.left;  
       }  
       else {  
         x=stack.pop();  
         x=x.right;  
       }  
     }  
     return res;  
   }  
 }  

1 条评论:

  1. It is a best solution found that very popular and helpful:
    https://www.youtube.com/watch?v=u2Py9rhxEuY&ab_channel=EricProgramming

    回复删除