算法基础|二叉树的遍历算法--中序非递归算法|Java实现

源自B站王卓老师的数据结构课程数据结构与算法基础（青岛大学-王卓）_哔哩哔哩_bilibili

第08周03--5.5遍历二叉树和线索二叉树5--二叉树的遍历算法--中序非递归算法

课程是C语言的，我写了个Java的实现，写了个大概，没细究是否有bug，我估计是有的。

    @Test
    public void test() {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(5);

        inOrder(root);

    }

    private static void inOrder(TreeNode root) {
        LinkedList stack = new LinkedList<>();
        stack.push(root);
        TreeNode node = stack.pop();

        while (node != null || !stack.isEmpty()){
            //如果当前操作节点的左节点为空，则输出该节点
            //如果不为空，则将该节点压入栈，并用左子节点覆盖该节点
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                node = stack.pop();
                System.out.println(node.val);
                node = node.right;
            }
        }
    }