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

Example:

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

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

 

方法一：递归

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    public void preorderTraversal(TreeNode root) {        if(root==null) return ;        preorderTraversal(root.left);        System.out.print(root.val+' ');        preorderTraversal(root.right);    }}

 

方法二：迭代

中序遍历第左右根，所以设计程序时首先要考虑的是找到最左边的叶子结点。找到之后弹出还要考虑这个结点有没有右孩子。

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    public List
     
       inorderTraversal(TreeNode root) {        Stack
      
        stack=new Stack
       
        ();        List
        
          list=new ArrayList
         
          ();        while (root!=null||!stack.isEmpty()){            while (root!=null){                stack.add(root);                root=root.left;            }            TreeNode treeNode=stack.pop();            list.add(treeNode.val);            root=treeNode.right;  //root是判断条件。每次弹出的结点都要检查是否还有右孩子。有就加入，没有就弹出。        }        return list;    }}