輸入：root = [1,null,2,3]
輸出：[1,3,2]

輸入：root = []
輸出：[]

輸入：root = [1]
輸出：[1]

/*
 有點麻煩，但還是自己寫出來了：首先一直找左子樹直到最左側節點，並將過程中的結點存到棧中；然後開始出棧，模擬的操作就是回溯，出棧過程中檢查每個結點是否有右子樹，
 沒有的話一直出棧並輸出節點信息；有的話該結點先不要出棧，進入右子樹重新執行上述過程。
 visited[i]是難點，你需要想到如果某個結點回溯過程中判斷有右子樹，那麼該節點不會出棧，但是會打印該結點信息（中序遍歷），需要使用visited[i]來記錄結點是否被打印過，避免重複打印
 p.right==null || visited[i]==true這個向上回溯的條件是難點，p.right==null容易想到，但是visited[i]==true不容易想，得模擬才能想到，
 要判斷visited[i]==true是因為向上回溯過程中該結點的右子樹可能已經被遍歷過了，只用p.right==null判斷能否向上回溯的話肯定是false，結果就會一直重複遍歷這課右子樹，導致死循環
 */
public class 二叉樹的中序遍歷 {
    // 遞歸
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root==null)return list;
        inorderSearch(root,list);
        return list;
    }
    void inorderSearch(TreeNode node, List list){
        if (node.left!=null) inorderSearch(node.left,list);
        list.add(node.val);
        if (node.right!=null) inorderSearch(node.right,list);
    }
    
    // 迭代
    public List<Integer> inorderTraversal1(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root==null)return list;
        Stack<TreeNode> rootNodes = new Stack<>();
        Boolean[] visited = new Boolean[128];
        int i = 0;
        TreeNode p = root;
        while(p!=null){
            // 遍歷進入以p為根結點的最左結點
            while (p!=null){
                rootNodes.push(p);
                p = p.left;
                visited[i++] = false;
            }
            // 出棧直到某個節點有右子樹
            p = rootNodes.peek();
            i--;
            // 向上回溯的條件：要麼沒有右子樹，要麼右子樹被遍歷過了
            while (p!=null && (p.right==null || visited[i]==true)){
                if (visited[i--]==false){
                    list.add(p.val);
                }
                rootNodes.pop();
                p = rootNodes.isEmpty() ? null:rootNodes.peek();
            }
            // 向上回溯過程中發現該結點有右子樹，那麼跳轉到右子樹，以當前結點為根結點重複上述循環
            if (p!=null){
                list.add(p.val);
                p = p.right;
                visited[i++] = true;
            }
        }
        return list;
    }