11. 二叉树-DFS (迭代)

正文

先序遍历（写法一）

class TreeNode(var value: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun preorderTraversal(root: TreeNode?) {
    val stack = LinkedList<TreeNode>()
    root ?: return
    stack.addFirst(root)

    while (!stack.isEmpty()) {
        val current = stack.removeFirst()
        visit(current)
        
        // 先将右子节点入栈，再将左子节点入栈
        if (current.right != null) {
            stack.addFirst(current.right)
        }
        if (current.left != null) {
            stack.addFirst(current.left)
        }
    }
}

fun visit(root: TreeNode){
    println(root.value)
}

先序遍历（写法二）

class TreeNode(var value: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun preorderTraversal(root: TreeNode?) {
    val stack = LinkedList<TreeNode>();
    var cur: TreeNode = root;

    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            visit(cur)
            stack.addFirst(cur);
            cur = cur.left;
        }

        val top: TreeNode = stack.removeFirst(();
        cur = top.right;
    }
}

fun visit(node: TreeNode){
    println(node.value)
}

中序遍历

class TreeNode(var value: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun inorderTraversal(root: TreeNode?) {
    val stack = LinkedList<TreeNode>();
    var cur: TreeNode = root;

    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            stack.addFirst(cur);
            cur = cur.left;
        }

        visit(cur)
        val top: TreeNode = stack.removeFirst(();
        cur = top.right;
    }
}

fun visit(node: TreeNode){
    println(node.value)
}

后序遍历

class TreeNode(var value: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun postorder(root: TreeNode?) {
    val stack: LinkList = LinkedList<TreeNode>()
    var cur = root
    var last = null
    
    while (cur != null || !stack.isEmpty()) {
        // 左节点先入栈
        while (cur != null) { 
            stack.addFirst(cur)                        // 第一次访问
            cur = cur.left
        }
        val top = stack.peekFirst()                    // 第二次访问
        if (top.right == null || top.right == last) {  // 第三次访问
            visit(top)
            last = top
            stack.removeFirst()
        } else {
            cur = top.right
        }
    }
}

fun visit(node: TreeNode){
    println(node.value)
}

非递归后续遍历比较有意思
结合注释我们来一语道破天机
先序，中序，后序遍历
第一次经过结点（从双亲过来）: 先序
第二次经过结点（从左孩子过来）: 中序
第三次经过结点（右孩子过来）: 后序