經典演算法 非遞歸遍歷二叉樹 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;
    }
}