题目要求

Given a binary tree, return the inorder traversal of its nodes' values.For example:Given binary tree [1,null,2,3],   1    \     2    /   3return [1,3,2].Note: Recursive solution is trivial, could you do it iteratively?

中序遍历树，并将遍历结果添加到数组中。分别用递归和循环的方式结局。

递归

核心的思路就是先递归左侧子节点，之后读取中间节点的值，再递归右侧子节点。

public List
    
      inorderTraversal(TreeNode root) {        List
     
       result = new ArrayList
      
       ();        inorderTraversal(root, result);        return result;    }        public void inorderTraversal(TreeNode root, List
       
         result){        if(root==null) return;        inorderTraversal(root.left, result);        result.add(root.val);        inorderTraversal(root.right, result);    }
       
      
     
    

循环

这里需要利用栈的数据结构。如果当前节点存在左子节点，则继续遍历左子树直到最后一个左子节点。然后依次处理栈中的元素。如果栈顶元素有右子节点，则将其右子节点压入栈中作为root，再继续遍历root的左子节点。当root和stack都为空时，遍历结束。

public List
    
      inorderTraversal2(TreeNode root) {        List
     
       result = new ArrayList
      
       ();        if(root==null) return result;                LinkedList
       
         stack = new LinkedList
        
         ();        do{            while(root!=null){                stack.push(root);                root = root.left;             }            root = stack.pop();            result.add(root.val);            root = root.right;        }while(!(stack.isEmpty() && root==null));        return result;    }