[leetcode]94. Binary Tree Inorder Traversal二叉树中序遍历

Given a binary tree, return the inorder traversal of its nodes' values.

Example:

Input: [1,null,2,3]
   1
    
     2
    /
   3

Output: [1,3,2]

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

题意：

二叉树中序遍历

Solution1: Recursion

code

 1 class Solution {
 2      public List<Integer> inorderTraversal(TreeNode root) {
 3          List<Integer> list = new ArrayList<>();
 4          storeInorder(root, list);
 5          return list;
 6      } 
 7     public void storeInorder(TreeNode node, List<Integer> list) {
 8         if(node == null)  return;
 9         storeInorder(node.left, list);
10         list.add(node.val);
11         storeInorder(node.right, list);
12     }   
13 }

Solution2: Iteration

code

 1 class Solution {
 2     public List<Integer> inorderTraversal(TreeNode root) {
 3         //left -- root -- right 
 4         ArrayList<Integer> result = new ArrayList<>();
 5         Stack<TreeNode> s = new Stack<>();
 6         TreeNode p  = root;
 7         
 8         while(!s.isEmpty() || p!=null){
 9             if(p!=null){
10                 s.push(p);
11                 p = p.left;
12             }else{
13                 p =s.pop();
14                 result.add(p.val);
15                 p = p.right;
16             }
17         }
18         return result;     
19     }
20 }