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

示例:

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

  1
      \
      2
    /
   3

输出: [1,3,2]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题在王道408中有讲到，但是记忆不是特别清晰了于是再写了一次

首先当然是最简单的递归写法

class Solution {

    public List<Integer> inorderTraversal(TreeNode root) {
         List<Integer>  list=new LinkedList<Integer>();
      
        return  help(root,list);
    }
    public List<Integer> help(TreeNode root,List list){
          if(root==null){
            return list;
        }
       help(root.left,list);
       list.add(root.val);
    
       help(root.right,list);
       return  list;
    }
   
}

接着重点来了 ，非递归写法 这就要用到栈了

          1
       2     3
     4  5   6  7  

输出的序列是 4251637 先走到最左 一次入栈 ，到底后出栈，访问该节点，接着访问访问其右子树 依然是走左走到底，同时入栈，到底后出栈

class Solution {
    //中序遍历 ： 先走到左子树底端 
   public List<Integer> inorderTraversal(TreeNode root) {
       
      List<Integer> list=new LinkedList<Integer>();
    if(root==null){
       return  list;
    }
       Stack<TreeNode> st  = new Stack<TreeNode>();
       while(root!=null||!st.isEmpty()){

           while(root!=null){
           //左子树一次入栈
           st.push(root);
           root=root.left;
           }
           //左子树入栈完成,应出栈栈顶节点，并且访问
           TreeNode temp= st.pop();
           //访问当前出栈节点
           list.add(temp.val);
           //将root置位 当前出栈节点的右子树 ，接着对右子树 走开始的流程：往左走，依次入栈
           root=temp.right;

           


       }
       //左子树已经入栈完成.

       return list;


    
   }
}