经典算法 非递归遍历二叉树 binary tree in order traversal without recursion

feellikelearning March 15, 2020 0 Comments

Binary in order traversal 一般是大多数人学习的第一个recursion算法，非常简单，3行就能写完。但这其实是compiler帮我们写了大部分的code，练习不用recursion能更好的帮助我们理解under the cover发生了什么。如果没练习过，其实还是不容易想到和写对的。

代码如下

Java

import java.util.Stack;
import TreeNode;

public class BstTraversal {
    public static void traversal(TreeNode root) {
        if (root == null)  {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        pushLeft(root, stack);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            System.out.println(cur.val);
            if (cur.right != null) {
                pushLeft(cur.right, stack);
            }
        }
    }

    public static void pushLeft(TreeNode node, Stack<TreeNode> stack) {
        TreeNode cur = node;
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
    }

    // test
    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;

        traversal(node1);
    }
}

其中TreeNode class如下

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public  TreeNode(int val) {
        this.val = val;
        left = null;
        right = null;
    }
}