中序遍历非递归

import java.util.*;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null ||  (pRootOfTree.left == null && pRootOfTree.right == null)) return pRootOfTree;
        // 中序遍历， 可以 从小到大
        TreeNode pre = null;
        LinkedList<TreeNode> st = new LinkedList<>();
        TreeNode temp = pRootOfTree;
        // 记录答案
        TreeNode ans = null;
        while (!st.isEmpty() || temp != null) {
            while (temp != null) {
                st.push(temp);
                temp = temp.left;
            }
            // 取出 当前值
            TreeNode n = st.poll(); //left 前， right 后
            if (pre != null) {
                pre.right = n;
            } else {
                ans = n;
            }
            n.left = pre;
            temp = n.right;
            pre = n;
        }
        return ans;
    }
}