94.二叉树的中序遍历

发布时间:2024年01月21日

迭代

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        // 当前节点不为空,就向左,如果为空就从栈中弹出一个节点,然后向右
        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {// root的左子树为空,那就记录root,访问右子树
                root = stack.pop();
                list.add(root.val);
                root = root.right;
            }
        }
        return list;
    }

和前序遍历的区别

最重要的区别是访问节点和记录节点的时间
在前序遍历中,首先访问根节点,记录根节点然后访问左子节点,符合前序遍历 中左右的顺序
而在中序遍历中,首先访问根节点,但是不记录,然后访问左子节点,当访问的节点没有左子节点时,才从栈中弹出一个节点并记录,然后转向右子节点。

文章来源:https://blog.csdn.net/qq_44047415/article/details/135731526
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。