Tuesday, July 29, 2014

[LeetCode] Binary Tree Inorder Traversal


Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3
return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?
confused what "{1,#,2,3}" means?

解题思路:
DSF,  先把所有的左结点存放到stack, pop的时候,print 当前位置的值,然后再遍历右子树

Java Code:

 public List inorderTraversal(TreeNode root) {
          Stack tmp = new Stack();
          List res = new ArrayList();
          
          TreeNode p = root;
          
          while( !tmp.isEmpty() || p != null ){
              while(p != null){
                  tmp.add(p);
                  p = p.left;
              }
           
               p = tmp.pop();
               res.add(p.val);
               p = p.right;
           
          }
          
        return res;
    }

No comments:

Post a Comment