02_二叉树的迭代遍历

简介: 02_二叉树的迭代遍历

二叉树的迭代遍历

// 前序遍历顺序:中-左-右,入栈顺序:中-右-左
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> 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;
    }
}
// 后序遍历顺序 左-右-中 入栈顺序:中-左-右 出栈顺序:中-右-左, 最后翻转结果
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;
    }
}
相关文章
在 Flutter 中如何使用 ChangeNotifierProvider 实现数据共享?
在 Flutter 中如何使用 ChangeNotifierProvider 实现数据共享?
|
网络协议 Linux Shell
CentOS7系统命令学习笔记(一)
CentOS7系统命令学习笔记(一)
275 12
|
存储 弹性计算 运维
阿里云容器服务Kubernetes版(ACK)部署与管理体验评测
阿里云容器服务Kubernetes版(ACK)是一个功能全面的托管Kubernetes服务,它为企业提供了快速、灵活的云上应用管理能力。
380 2
|
算法
阿里云图像搜索应用篇-家具家居图片搜索
阿里云图像搜索产品于2022年3月17日正式发布家具家居图像搜索模型,通过大规模算法模型训练,可在海量图片素材中快速定位到与原图中的同款或相似款家居或家具图片,识别过程中可有效避免图片翻转、局部、颜色变换、款式微调、花纹变换等情况对搜索结果的影响,针对床上用品、家具、室内设计图等多个场景可快速找到相似图片或商品。可广泛应用于室内设计图片素材网站、 家纺类电商网站、家具家居类电商网站以及各种内容导购网站等。
880 0
阿里云图像搜索应用篇-家具家居图片搜索
|
SQL 弹性计算 人工智能
阿里云云防火墙评测
对阿里云云防火墙进行全面评测
2052 1
阿里云云防火墙评测
一分钟看懂Python中的 // 和 / 和 % 的用法区别
一分钟看懂Python中的 // 和 / 和 % 的用法区别
|
存储 对象存储 安全
开箱即用-OSS无代理备份
OSS对象存储作为阿里云上海量,安全,低成本,高可靠的云存储服务,越来越多的数据放在OSS存储上。随着数据量的增长,误删除,数据错误修改等操作所造成的损失也越加巨大。 混合云备份(HBR)最近推出OSS备份无代理服务,能够非常轻松的将OSS当中的数据保护起来。
6535 0
开箱即用-OSS无代理备份