代码编织梦想

二叉树的中序遍历

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

示例 1:

在这里插入图片描述

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

示例 2:

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

示例 3:

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

Morris 遍历

思路:

Morris 遍历算法是另一种遍历二叉树的方法,它能将非递归的中序遍历空间复杂度降为 O ( 1 ) O(1) O(1)
Morris 遍历算法整体步骤如下(假设当前遍历到的节点为 x x x):

  1. 如果 x x x 无左孩子,先将 x x x 的值加入答案数组,再访问 x x x 的右孩子,即 x = x . r i g h t x=x.right x=x.right
  2. 如果 x 有左孩子,则找到 x 左子树上最右的节点(即左子树中序遍历的最后一个节点, x x x 在中序遍历中的前驱节点),我们记为 p r e d e c e s s o r predecessor predecessor。根据 p r e d e c e s s o r predecessor predecessor 的右孩子是否为空,进行如下操作。
    • 如果 p r e d e c e s s o r predecessor predecessor 的右孩子为空,则将其右孩子指向 x x x,然后访问 x x x 的左孩子,即 x = x . l e f t x=x.left x=x.left
    • 如果 p r e d e c e s s o r predecessor predecessor 的右孩子不为空,则此时其右孩子指向 x x x,说明我们已经遍历完 x x x 的左子树,我们将 p r e d e c e s s o r predecessor predecessor 的右孩子置空,将 x x x 的值加入答案数组,然后访问 x x x 的右孩子,即 x = x . r i g h t x=x.right x=x.right
  3. 重复上述操作,直至访问完整棵树。

时间复杂度: O ( n ) O(n) O(n),其中 n n n 为二叉搜索树的节点个数。Morris 遍历中每个节点会被访问两次,因此总时间复杂度为 O ( 2 n ) = O ( n ) O(2n)=O(n) O(2n)=O(n)
空间复杂度: O ( 1 ) O(1) O(1)

# 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]:
        results = []
        most_right = None
        while root:
            most_right = root.left
            if most_right:
                while most_right.right and most_right.right != root:
                    most_right = most_right.right
                if not most_right.right:
                    most_right.right = root
                    root = root.left
                    continue
                else:
                    most_right.right = None
            results.append(root.val)
            root = root.right
        return results

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/binary-tree-inorder-traversal/

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_45616285/article/details/128013207

数据结构与算法-二叉树中序遍历_interstellar-ai的博客-爱代码爱编程

二叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树,有前序、中序以及后序三种遍历方法。因为树的定义本身就 是递归定义,因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而

二叉树中序遍历--【非递归】c语言栈实现_qiki_tang的博客-爱代码爱编程

leetcode94 Binary Tree inorder Traversal 一、问题描述 给定一个二叉树,返回它的节点值的中序遍历。---使用非递归实现 【举例】输入 [1,null,2,3]    1     \      2     /    3 输出 [1,2,3] 二、解题思路非递归实现--使用栈 中序遍历:左根右 从当前节点T出发,压

【算法】二叉树的前序遍历/中序遍历/后序遍历详解-爱代码爱编程

这个来自leetcode的第144个问题。(中等难度) 问题描述:给定一个二叉树,返回它的 前序 遍历。 相信我们在上学期间(计算机相关专业的)已经学过二叉树,既然决定写这一篇博客,那么就从头开始复习加学习。 二叉树:       定义:二叉树是n(n>=0)个结点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的

C语言 中序遍历二叉树--非递归算法-爱代码爱编程

完整代码如下: #include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct BiTNode//二叉树的结构体 { char ch;//二叉树的数据域 struct BiTNode *lchild,*rchild;//二叉树

算法题-二叉树的中序遍历-爱代码爱编程

C++解二叉树的中序遍历 原题: 给定一个二叉树的根节点 root ,返回它的 中序 遍历。 示例 1: 输入:root = [1,null,2,3] 输出:[1,3,2] 示例 2: 输入:root = [] 输出:[] 示例 3: 输入:root = [1] 输出:[1] 示例 4: 输入:root = [1,2] 输出:[2,1] 示例 5:

二叉树—二叉树的中序遍历(leetcode 94)-爱代码爱编程

题目描述 给定一个二叉树的根节点 root ,返回它的 中序 遍历。 示例 1: 输入:root = [1,null,2,3] 输出:[1,3,2] 示例 2: 输入:root = [] 输出:[] 示例 3: 输入:root = [1] 输出:[1] 示例 4: 输入:root = [1,2] 输出:[

二叉树的中序遍历-python-爱代码爱编程

leetCode第94题 二叉树的中序遍历 给定一个二叉树的根节点 root ,返回它的 中序 遍历。链接:https://leetcode-cn.com/problems/binary-tree-inorder-traversal 示例 1: 输入:root = [1,null,2,3] 输出:[1,3,2] 示例 2: 输入:roo

【二叉树】剑指offer:二叉树中序遍历的下一个节点-爱代码爱编程

 思路一:vector存放中序遍历,然后查找输出 注意: pNode是待查找节点,因为要通过父节点遍历二叉树,所以首先要找到父节点 TreeNode *temp=t; TreeNode *root; while(temp->next){ temp=temp->next; } root=temp; struct TreeLin

力扣热门100题——二叉树的中序遍历(递归,迭代,Morris 中序遍历)-爱代码爱编程

7、二叉树的中序遍历 1.问题描述 给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。 2.示例 示例 1: 输入:root = [1,null,2,3] 输出:[1,3,2] 示例 2: 输入:root = [] 输出:[] 示例 3: 输入:root = [1] 输出:[1] 3.提示 树中节点数目在范围 [0, 100]

(数据结构)二叉树中序遍历-爱代码爱编程

二叉树中序遍历 二叉树中序遍历的实现思想是: 访问当前节点的左子树访问根节点访问当前节点的右子树 图 1 二叉树 以上图 1 为例,中序遍历的过程如下: 访问该二叉树的根节点,找到 1遍历节点 1 的左子树,找到节点 2遍历节点 2 的左子树,找到节点 4由于节点 4 无左孩子,因此找到节点 4,并遍历节点 4 的右子树由于节点 4 无右子

c语言:二叉树的中序遍历_胖头小奶虎的博客-爱代码爱编程

算法思路 若 p 所指结点不为空,则将该结点的地址 p 入栈,然后再将 p 指向其左孩子结点;若 p 所指向的结点为空,则从堆栈中退出栈顶元素(某个结点的地址)送 p,并访问该结点,然后再将 p 指向该结点的右孩子结点。重