94. Binary Tree Inorder Traversal

题目描述

Given a binary tree, return theinordertraversal of its nodes' values.

For example:
Given binary tree[1,null,2,3],

解题方法

     //Non-recursive
    /*public List<Integer> inorderTraversal(TreeNode root){
        if(root == null){
            return new ArrayList<Integer>();
        }
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode node = stack.pop();
            cur = node.right;
            list.add(node.val);
        }
        return list;
    }*/

    //DFS
    /*public List<Integer> inorderTraversal(TreeNode root){
        List<Integer> lists = new ArrayList<>();
        DFS(root, lists);
        return lists;
    }

    private void DFS(TreeNode root, List<Integer> lists){
        if(root == null){
            return;
        }
        DFS(root.left, lists);
        lists.add(root.val);
        DFS(root.right, lists);
    }*/

    //Divide and Conquer
    public List<Integer> inorderTraversal(TreeNode root){
        List<Integer> lists = new ArrayList<>();
        if(root == null){
            return lists;
        }

        List<Integer> left = inorderTraversal(root.left);
        List<Integer> right = inorderTraversal(root.right);
        lists.addAll(left);
        lists.add(root.val);
        lists.addAll(right);
        return lists;
    }