Binary Tree Inorder Traversal

• LintCode: No.67-Binary Tree Inorder Traversal
• Problem:

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

• Example:

  Given binary tree {1,#,2,3},
    1
     \
      2
     /
    3 
  return [1,3,2].
  

• Analysis:

  Inorder Traversal : visited Left child, current node,and Right child recursively
  

• Java:

  • Recursive:

    public class Solution {
        public ArrayList<Integer> inorderTraversal(TreeNode root) {
            ArrayList<Integer> result = new ArrayList<Integer>();
            traverse(root, result);
            return result;
        }
        public void traverse(TreeNode node, ArrayList<Integer> result) {
            if (node == null) {
                return;
            }
            traverse(node.left, result);
            result.add(node.val);
            traverse(node.right, result);
            return;
        }
    }
    

• Time Complexity:

  • O(n), n is the number of nodes