二叉树的中序遍历

94. 二叉树的中序遍历

给定一个二叉树，返回它的中序 遍历。

示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    /*
    * 中序遍历 “左根右”。需要一个栈来保存根结点。
    * 当访问过树的最左叶子结点后，弹出根结点，访问根结点，继续访问根节点的右子结点。
    */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> s = new Stack<>();

        //循环条件：栈中元素不为空。树的根结点非空
       while(root != null || ! s.isEmpty()){
           if(root != null){
               //根结点入栈
               s.push(root);
               //继续入栈根结点的左子结点
               root = root.left;
           }
           else{
               //无左子结点，将根结点出栈
               root = s.pop();
               //访问根结点
               res.add(root.val);
               //继续访问根结点的右子结点
               root = root.right;
           }
       }

        return res;
    }

}