算法leetcode|94. 二叉树的中序遍历(多语言实现)


文章目录

  • 94. 二叉树的中序遍历:
    • 样例 1:
    • 样例 2:
    • 样例 3:
    • 提示:
  • 分析:
  • 题解:
    • rust:
    • go:
    • c++:
    • python:
    • java:


94. 二叉树的中序遍历:

给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。

样例 1:

输入:
	
	root = [1,null,2,3]
	
输出:
	
	[1,3,2]

样例 2:

输入:
	
	root = []
	
输出:
	
	[]

样例 3:

输入:
	
	root = [1]
	
输出:
	
	[1]

提示:

  • 树中节点数目在范围 [0, 100]
  • -100 <= Node.val <= 100

分析:

  • 面对这道算法题目,二当家的再次陷入了沉思。
  • 二叉树的中序遍历和前序遍历,后续遍历是二叉树常用的遍历方式。
  • 使用递归方式比循环非递归方式更加简单,直观,易于理解。
  • 通常二叉树的中序遍历一定要使用一个栈结构,因为中序遍历的要求是遍历完左子树才能遍历当前节点,但是遍历到了左子树就无法再回到当前节点了,所以一般都是使用压栈的方式,先将当前节点压栈,遍历完左子树再将当前节点出栈,这样空间复杂度就会是 O(n) (递归也相当于使用了栈结构)。
  • 说起来这不是什么大问题,但是算法就是要想办法优化降低时间和空间的复杂度,于是寄出一种可以将空间复杂度降低为 O(1) 的中序遍历方式,Morris 中序遍历。
  • 事实上Morris 中序遍历不是没有代价的,由于要做额外的节点连接和恢复,相当于用时间换空间。

题解:

rust:

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn inorder_traversal(mut root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut ans = Vec::new();

        while root != None {
            if root.as_ref().unwrap().borrow().left != None {
                // 寻找当前 root 节点的前驱节点:前驱 predecessor 节点就是当前 root 节点向左走一步,然后一直向右走至无法走为止
                let mut predecessor = root.as_ref().unwrap().borrow().left.clone();
                while predecessor.as_ref().unwrap().borrow().right != None
                    && predecessor.as_ref().unwrap().borrow().right != root {
                    predecessor = predecessor.unwrap().borrow().right.clone();
                }

                if predecessor.as_ref().unwrap().borrow().right == None {
                    // 让前驱 predecessor 节点的右指针指向当前 root 节点,继续遍历左子树,之后会再次回到当前 root 节点
                    predecessor.unwrap().borrow_mut().right = root.clone();
                    // 遍历左子树
                    root = root.unwrap().borrow().left.clone();
                    continue;
                } else {
                    // 左子树遍历完毕又回到了当前 root 节点,让前驱 predecessor 节点的右指针与当前 root 节点断开,恢复原样
                    predecessor.unwrap().borrow_mut().right = None;
                }
            }
            // 遍历当前 root 节点
            ans.push(root.as_ref().unwrap().borrow().val);
            // 遍历当前 root 节点的右子树
            root = root.unwrap().borrow().right.clone();
        }

        return ans;
    }
}

go:

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    var ans []int

	for root != nil {
		if root.Left != nil {
			// 寻找当前 root 节点的前驱节点:前驱 predecessor 节点就是当前 root 节点向左走一步,然后一直向右走至无法走为止
			predecessor := root.Left
			for predecessor.Right != nil && predecessor.Right != root {
				// 有右子树且没有设置过指向 root,则继续向右走
				predecessor = predecessor.Right
			}

			if predecessor.Right == nil {
				// 让前驱 predecessor 节点的右指针指向当前 root 节点,继续遍历左子树,之后会再次回到当前 root 节点
				predecessor.Right = root
				// 遍历左子树
				root = root.Left
				continue
			} else {
				// 左子树遍历完毕又回到了当前 root 节点,让前驱 predecessor 节点的右指针与当前 root 节点断开,恢复原样
				predecessor.Right = nil
			}
		}
		// 遍历当前 root 节点
		ans = append(ans, root.Val)
		// 遍历当前 root 节点的右子树
		root = root.Right
	}

	return ans
}

c++:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;

        while (root != nullptr) {
            if (root->left != nullptr) {
                // 寻找当前 root 节点的前驱节点:前驱 predecessor 节点就是当前 root 节点向左走一步,然后一直向右走至无法走为止
                TreeNode *predecessor = root->left;
                while (predecessor->right != nullptr && predecessor->right != root) {
                    predecessor = predecessor->right;
                }

                if (predecessor->right == nullptr) {
                    // 让前驱 predecessor 节点的右指针指向当前 root 节点,继续遍历左子树,之后会再次回到当前 root 节点
                    predecessor->right = root;
                    // 遍历左子树
                    root = root->left;
                    continue;
                } else {
                    // 左子树遍历完毕又回到了当前 root 节点,让前驱 predecessor 节点的右指针与当前 root 节点断开,恢复原样
                    predecessor->right = nullptr;
                }
            }
            // 遍历当前 root 节点
            ans.emplace_back(root->val);
            // 遍历当前 root 节点的右子树
            root = root->right;
        }

        return ans;
    }
};

python:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = list()

        while root is not None:
            if root.left is not None:
                # 寻找当前 root 节点的前驱节点:前驱 predecessor 节点就是当前 root 节点向左走一步,然后一直向右走至无法走为止
                predecessor = root.left
                while predecessor.right is not None and predecessor.right != root:
                    # 有右子树且没有设置过指向 root,则继续向右走
                    predecessor = predecessor.right

                if predecessor.right is None:
                    # 让前驱 predecessor 节点的右指针指向当前 root 节点,继续遍历左子树,之后会再次回到当前 root 节点
                    predecessor.right = root
                    # 遍历左子树
                    root = root.left
                    continue
                else:
                    # 左子树遍历完毕又回到了当前 root 节点,让前驱 predecessor 节点的右指针与当前 root 节点断开,恢复原样
                    predecessor.right = None
            # 遍历当前 root 节点
            ans.append(root.val)
            # 遍历当前 root 节点的右子树
            root = root.right

        return ans


java:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<Integer>();

        while (root != null) {
            if (root.left != null) {
                // 寻找当前 root 节点的前驱节点:前驱 predecessor 节点就是当前 root 节点向左走一步,然后一直向右走至无法走为止
                TreeNode predecessor = root.left;
                while (predecessor.right != null && predecessor.right != root) {
                    predecessor = predecessor.right;
                }

                if (predecessor.right == null) {
                    // 让前驱 predecessor 节点的右指针指向当前 root 节点,继续遍历左子树,之后会再次回到当前 root 节点
                    predecessor.right = root;
                    // 遍历左子树
                    root = root.left;
                    continue;
                } else {
                    // 左子树遍历完毕又回到了当前 root 节点,让前驱 predecessor 节点的右指针与当前 root 节点断开,恢复原样
                    predecessor.right = null;
                }
            }
            // 遍历当前 root 节点
            ans.add(root.val);
            // 遍历当前 root 节点的右子树
            root = root.right;
        }

        return ans;
    }
}

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】三连走一波~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子:https://le-yi.blog.csdn.net/ 博客原创~


本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/272184.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

什么样的产品适合建设私域流量池?

私域流量是什么&#xff1f;公域流量和私域流量是相对概念&#xff0c;触达和运营更加自由的流量称为私域流 量。私域流量的形态&#xff0c;我们称为私域流量池。私域流量池本质是便捷和低成本的运营方式&#xff0c; 运营用户&#xff0c;追求更便宜的流量来源、更高的售卖转…

什么是动态IP?静态IP和动态IP有什么区别?

动态IP(Dynamic IP)和静态IP(Static IP)它是指在计算机网络中分配给设备的两种不同类型的IP地址。 动态IP是指每次设备连接到网络时&#xff0c;网络服务提供商(ISP)IP地址的动态分配。当设备重新连接到网络时&#xff0c;它可能会被分配到不同的IP地址。动态IP适用于传统的家…

通过IntersectionObserver实现图片下拉加载(瀑布流布局)

效果展示&#xff1a; 瀑布流上拉加载 目录结构 html: <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8" /><meta http-equiv"X-UA-Compatible" content"IEedge" /><meta name"vie…

力扣刷题记录(18)LeetCode:474、518、377、322

目录 474. 一和零 518. 零钱兑换 II 377. 组合总和 Ⅳ 322. 零钱兑换 总结&#xff1a; 474. 一和零 这道题和前面的思路一样&#xff0c;就是需要将背包扩展到二维。 class Solution { public:int findMaxForm(vector<string>& strs, int m, int n) {vector&l…

KNN与KD树博客总结

目录 总结小结&#xff1a; 总结 原始篇&#xff1a;KNN算法及其优缺点算法思想改进篇&#xff1a;KD树&#xff08;KNN的plus版算法实现第一篇&#xff1a;平衡二叉树的构建&#xff08;递归算法实现第二篇&#xff1a;KD树的构建&#xff08;递归算法实现第三篇&#xff1a;…

开源持续测试平台Linux MeterSphere本地部署与远程访问

文章目录 前言1. 安装MeterSphere2. 本地访问MeterSphere3. 安装 cpolar内网穿透软件4. 配置MeterSphere公网访问地址5. 公网远程访问MeterSphere6. 固定MeterSphere公网地址 前言 MeterSphere 是一站式开源持续测试平台, 涵盖测试跟踪、接口测试、UI 测试和性能测试等功能&am…

windows安全配置实验手册

访问控制策略&#xff08;L1940520022J&#xff09; 预备知识 Windows 7中&#xff0c;不仅有面向软件的限制方法&#xff0c;还增加了一种名为AppLocker的访问控制策略&#xff08;仅适用于企业版和旗舰版&#xff09;。 实验环境 操作系统类型&#xff1a;windows 7。 实…

【问题记录-ASIO】Audition多通道ASIO驱动提示“(不工作)“问题

一&#xff0c;问题现象 在使用Audition打开多通道工程&#xff0c;使用ASIO驱动&#xff0c;却发现设备提示“不工作”&#xff0c;如下图所示&#xff1a; 二&#xff0c;解决方法 2.1 声卡设备枚举确认 首先确认声卡设备枚举是否成功&#xff0c;如果没有枚举成功&…

【SpringCloud笔记】(10)消息总线之Bus

Bus 前言 戳我了解Config 学习Config中我们遇到了一个问题&#xff1a; 当我们修改了GitHub上配置文件内容&#xff0c;微服务需要配置动态刷新并且需要手动向客户端发送post请求刷新微服务之后才能获取到GitHub修改过后的内容 假如有多个微服务客户端3355/3366/3377…等等…

将本地镜像推送到阿里云

文章目录 创建仓库镜像登录 并上传下载上传的 创建仓库镜像 利用下面的脚本进行配置 登录 并上传 [roothadoop100 ~]# docker login --username13thm registry.cn-hangzhou.aliyuncs.com Password: [roothadoop100 ~]# docker tag ba78e6d6845c registry-vpc.cn-hangzhou.al…

C++-类和对象(1)

1.面向过程和面向对象初步认识 C语言是面向过程的&#xff0c;关注的是过程&#xff0c;分析出求解问题的步骤&#xff0c;通过函数调用逐步解决问题。 C是基于面向对象的&#xff0c;关注的是对象&#xff0c;将一件事情拆分成不同的对象&#xff0c;靠对象之间的交互完 成。…

一文读懂铭文赛道新手攻略

近期&#xff0c;加密领域的热点焦点不断涌现&#xff0c;但毫无疑问&#xff0c;"铭文"这个词汇已经成为了近两个月内广受瞩目的关键词之一。像ORDI、SATS、RATS等铭文项目在比特币区块链上获得了惊人的增长&#xff0c;为持有者带来了巨大的财富效应。铭文热潮已经…

使用 Fiddler+Linux 日志 + 数据库,搞懂3个问题,强势回怼开发!

测试过程中有没有遇到过什么问题是你解决的&#xff1f; 遇到bug怎么分析是前端bug还是后端bug&#xff1f; 测试的时候怎么确认你的测试结果是正确的&#xff1f; 定位分析问题的能力是测试不可或缺的&#xff0c;而且这个能力需要项目经验积累以及需要丰富的知识面才能达到…

k8s---kubernets

目录 一、Kurbernetes 1.2、K8S的特性&#xff1a; 1.3、docker和K8S&#xff1a; 1.4、K8S的作用&#xff1a; 1.5、K8S的特性&#xff1a; 二、K8S集群架构与组件&#xff1a; 三、K8S的核心组件&#xff1a; 一、master组件&#xff1a; 1、kube-apiserver&#xff1…

NET中使用SQLSugar操作sqlserver数据库

目录 一、SqlSugar是什么&#xff1f; 二、迁移和建表 1.建立实体 2.创建上下文类 3.在Program中添加SqlSugar服务 4.在控制器中注入上下文类 三、简单实现CURD功能 总结 一、SqlSugar是什么&#xff1f; SqlSugar是一款老牌 .NET 开源ORM框架。 主要特点&#xff1a…

JVM入门到入土-Java虚拟机寄存器指令集与栈指令集

JVM入门到入土-Java虚拟机寄存器指令集与栈指令集 HotSpot虚拟机中的任何操作都需要入栈和出栈的步骤。 由于跨平台性的设计&#xff0c;Java的指令都是根据栈来设计的。不同平台CPU架构不同&#xff0c;所以不能设计为基于寄存器的。优点是跨平台&#xff0c;指令集小&#x…

华为设备VRP系统管理

为了满足企业业务对网络的需求&#xff0c;网络设备中的系统文件需要不断进行升级。另外&#xff0c;网络设备中的配置文件也需要时常进行备份&#xff0c;以防设备故障或其他灾害给业务带来损害。在升级和备份系统文件或配置文件时&#xff0c;经常会使用FTP和TFTP来传输文件。…

系统学习Python——装饰器:函数装饰器-[跟踪调用]

分类目录&#xff1a;《系统学习Python》总目录 如下的代码定义并使用了一个函数装饰器&#xff0c;统计对被装饰函数的调用次数&#xff0c;并且针对每一次调用打印跟踪信息&#xff1a; class tracer:def __init__(self, func):self.calls 0self.func funcdef __call__(se…

【Linux驱动】最基本的驱动框架 | LED驱动

&#x1f431;作者&#xff1a;一只大喵咪1201 &#x1f431;专栏&#xff1a;《Linux驱动》 &#x1f525;格言&#xff1a;你只管努力&#xff0c;剩下的交给时间&#xff01; 目录 &#x1f3c0;最基本的驱动框架⚽驱动程序框架⚽编程 &#x1f3c0;LED驱动⚽配置GPIO⚽编程…

Python 高级(四):线程池 ThreadPoolExecutor

大家好&#xff0c;我是水滴~~ 当涉及到需要同时处理多个任务的情况时&#xff0c;使用线程池是一种高效的方法。Python提供了concurrent.futures模块&#xff0c;其中的ThreadPoolExecutor类使得使用线程池变得非常方便。本文将详细介绍Python线程池的概念、使用方法和示例代…