leetcode hot 100

发布时间:2024年01月24日

二叉树遍历(迭代)

在这里插入图片描述
二叉树的遍历不仅可以用递归来做,也可以用迭代来做。二叉树的递归底层是采用栈来进行的,所以我们迭代就要采用栈来做。

我们知道,栈的原则是先进后出,以前序为例,顺序是中左右,那么,以根节点开始,如果不为空,我们先把根节点压入栈,然后弹出,然后再把右节点压入栈,再把左节点压入栈,之后再按顺序弹出即可。

// 前序遍历顺序:中-左-右,入栈顺序:中-右-左
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right != null){
                stack.push(node.right);
            }
            if (node.left != null){
                stack.push(node.left);
            }
        }
        return result;
    }
}

与前序做对比的是后续,只需要记住,将前序进栈的顺序倒过来,最后再反转数组即可

// 后序遍历顺序 左-右-中 入栈顺序:中-左-右 出栈顺序:中-右-左, 最后翻转结果
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.left != null){
                stack.push(node.left);
            }
            if (node.right != null){
                stack.push(node.right);
            }
        }
        Collections.reverse(result);
        return result;
    }
}

中序就与前后序不同了,中序过程中,我们的顺序应该是左右中,所以,我们要处理的节点不是我们遍历到的节点,我们可以用一个指针来记录我们遍历到的节点,并使其进栈,之后遍历其左右节点即可

// 中序遍历顺序: 左-中-右 入栈顺序: 左-右
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()){
           if (cur != null){
               stack.push(cur);
               cur = cur.left;
           }else{
               cur = stack.pop();
               result.add(cur.val);
               cur = cur.right;
           }
        }
        return result;
    }
}
文章来源:https://blog.csdn.net/buptlzl/article/details/135680088
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。