題目：94. Binary Tree Inorder Traversal

連結：https://leetcode.com/problems/binary-tree-inorder-traversal/description/

• 等級：Easy

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

• Time complexity: O(n)
• Space complexity: O(n)

題目：102. Binary Tree Level Order Traversal

連結：https://leetcode.com/problems/binary-tree-level-order-traversal/description/

• 等級：Medium

解題思路

1. 使用index紀錄binary tree level

class Solution {
    private void preOrder(TreeNode root,int level,List<List<Integer>> save)
    {
        if (root == null)
            return;
        if (save.size() == level)
        {
            List<Integer> li = new ArrayList<Integer>();
            li.add(root.val);
            save.add(li);
        }
        else
        {
            save.get(level).add(root.val);
        }
        preOrder(root.left,level+1,save);
        preOrder(root.right,level+1,save);
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> save = new ArrayList<List<Integer>>();
        preOrder(root,0,save);
        return save;        
    }
}

• Time complexity: O(n)
• Space complexity: O(n)