博客

传送门

把原本的递归形式转换成迭代的形式，但是整体的思想还是不变的，

其实就是把递归的过程 翻译 成while + if 。

LeetCode94.二叉树的中序遍历（非递归）

方法1.

Morris Traversal 线索树


时间是O(n) 空间O（1）的解法 ：

参考：

https://blog.csdn.net/dxx707099957/article/details/88550437?utm_medium=distribute.pc_relevant.none-task-blog-title-2&spm=1001.2101.3001.4242

要使用O(1)空间进行遍历，最大的难点在于，遍历到子节点的时候怎样重新返回到父节点（假设节点中没有指向父节点的p指针），由于不能用栈作为辅助空间。为了解决这个问题，Morris方法用到了线索二叉树（threaded binary tree）的概念。在Morris方法中不需要为每个节点额外分配指针指向其前驱（predecessor）和后继节点（successor），只需要利用叶子节点中的左右空指针指向某种顺序遍历下的前驱节点或后继节点就可以了。

	public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans= new ArrayList<>();
        TreeNode cur = root, pre = null;
        while (cur != null) {
            if (cur.left == null) {
                ans.add(cur.val);
                cur = cur.right;// 前进，可能到真正的右儿子，也可能是下一个节点
            } else {
                pre = cur.left;
                while (pre.right != null && pre.right != cur) pre = pre.right;
                if (pre.right == null) { //右儿子是空
                    pre.right = cur;
                    cur = cur.left; // 并不是前进，相当于递归找cur.left的前驱
                } else { // 右儿子是cur，说明指针已经被置为下一个节点了
                    ans.add(cur.val);
                    pre.right = null;
                    cur = cur.right;//前进，一定是下一个节点
                }
            }
        }
        return ans;
    }

方法2；用栈

	public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        Stack<TreeNode> stk = new Stack<>();
        TreeNode leftNode = root;
        while (leftNode != null) {//先特殊处理root的左链
            stk.push(leftNode);
            leftNode = leftNode.left;
        }
        while (!stk.empty()) {
            TreeNode tmp = stk.pop();
            ans.add(tmp.val);
            tmp = tmp.right;
            while (tmp != null) {
                stk.push(tmp);
                tmp = tmp.left;
            }
        }
        return ans;  
	}

144. 二叉树的前序遍历（非递归）

	public List<Integer> preorderTraversal(TreeNode root) {
        LinkedList<Integer> ans = new LinkedList<>();
        if (root == null) return ans;
        Stack<TreeNode> stk = new Stack<>();
        stk.push(root);
        while (!stk.empty()) {
            TreeNode p = stk.pop();
            ans.add(p.val);
            if (p.right != null) stk.push(p.right);
            if (p.left != null) stk.push(p.left);
        }
        return ans;
     }

145. 二叉树的后序遍历（非递归）

	public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> ans = new LinkedList<>();
        if (root == null) return ans;
        Stack<TreeNode> stk = new Stack<>();
        stk.push(root);
        while (!stk.empty()) {
            TreeNode tmp = stk.pop();
            ans.addFirst(tmp.val);
            if (tmp.left != null) stk.push(tmp.left);
            if (tmp.right != null) stk.push(tmp.right);
        }
        return ans;
	}