二叉树题目:二叉树的中序遍历

这篇具有很好参考价值的文章主要介绍了二叉树题目:二叉树的中序遍历。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目

标题和出处

标题:二叉树的中序遍历

出处:94. 二叉树的中序遍历

难度

3 级

题目描述

要求

给你二叉树的根结点 root \texttt{root} root,返回其结点值的中序遍历。

示例

示例 1:

二叉树题目:二叉树的中序遍历

输入: root   =   [1,null,2,3] \texttt{root = [1,null,2,3]} root = [1,null,2,3]
输出: [1,3,2] \texttt{[1,3,2]} [1,3,2]

示例 2:

输入: root   =   [] \texttt{root = []} root = []
输出: [] \texttt{[]} []

示例 3:

输入: root   =   [1] \texttt{root = [1]} root = [1]
输出: [1] \texttt{[1]} [1]

数据范围

  • 树中结点数目在范围 [0,   100] \texttt{[0, 100]} [0, 100]
  • -100 ≤ Node.val ≤ 100 \texttt{-100} \le \texttt{Node.val} \le \texttt{100} -100Node.val100

进阶

递归解法很简单,你可以使用迭代解法完成吗?

解法一

思路和算法

二叉树的中序遍历的方法为:依次遍历左子树、根结点和右子树,对于左子树和右子树使用同样的方法遍历。由于遍历过程具有递归的性质,因此可以使用递归的方法实现二叉树的中序遍历。

递归的终止条件是当前结点为空。对于非终止条件,递归的做法如下。

  1. 对当前结点的左子树调用递归。

  2. 将当前结点的结点值加入中序遍历序列。

  3. 对当前结点的右子树调用递归。

遍历结束之后即可得到中序遍历序列。

代码

class Solution {
    List<Integer> traversal = new ArrayList<Integer>();

    public List<Integer> inorderTraversal(TreeNode root) {
        inorder(root);
        return traversal;
    }

    public void inorder(TreeNode node) {
        if (node == null) {
            return;
        }
        inorder(node.left);
        traversal.add(node.val);
        inorder(node.right);
    }
}

复杂度分析

  • 时间复杂度: O ( n ) O(n) O(n),其中 n n n 是二叉树的结点数。每个结点都被访问一次。

  • 空间复杂度: O ( n ) O(n) O(n),其中 n n n 是二叉树的结点数。空间复杂度主要是递归调用的栈空间,取决于二叉树的高度,最坏情况下二叉树的高度是 O ( n ) O(n) O(n)

解法二

思路和算法

使用迭代的方法实现二叉树的中序遍历,则需要使用栈存储结点。

从根结点开始遍历,遍历的终止条件是栈为空且当前结点为空。遍历的做法如下。

  1. 如果当前结点不为空,则将当前结点入栈,然后将当前结点移动到其左子结点,重复该操作直到当前结点为空。

  2. 将一个结点出栈,将当前结点设为出栈结点,将当前结点的结点值加入中序遍历序列。

  3. 将当前结点移动到其右子结点。

  4. 重复上述操作,直到达到遍历的终止条件。

代码

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> traversal = new ArrayList<Integer>();
        Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            traversal.add(node.val);
            node = node.right;
        }
        return traversal;
    }
}

复杂度分析

  • 时间复杂度: O ( n ) O(n) O(n),其中 n n n 是二叉树的结点数。每个结点都被访问一次。

  • 空间复杂度: O ( n ) O(n) O(n),其中 n n n 是二叉树的结点数。空间复杂度主要是栈空间,取决于二叉树的高度,最坏情况下二叉树的高度是 O ( n ) O(n) O(n)

解法三

思路和算法

莫里斯遍历是使用常数空间遍历二叉树的方法,由 J. H. Morris 提出。莫里斯遍历的核心思想是利用二叉树的空闲指针维护遍历顺序,达到省略栈空间的目的。

从根结点开始遍历,遍历的终止条件是当前结点为空。

对于每个结点,判断当前结点的左子树是否为空,执行相应的操作。

  • 如果当前结点的左子树为空,则将当前结点的结点值加入中序遍历序列,将当前结点移动到其右子结点。

  • 如果当前结点的左子树不为空,则找到当前结点的前驱结点,前驱结点为当前结点的左子树中的最右边的结点,判断前驱结点的右子结点是否为空。

    • 如果前驱结点的右子结点为空,则将前驱结点的右子结点设为当前结点,将当前结点移动到其左子结点。

    • 如果前驱结点的右子结点不为空,则将前驱结点的右子结点设为空,将当前结点的结点值加入中序遍历序列,将当前结点移动到其右子结点。

重复上述操作,直到达到遍历的终止条件。

代码

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> traversal = new ArrayList<Integer>();
        TreeNode node = root;
        while (node != null) {
            if (node.left == null) {
                traversal.add(node.val);
                node = node.right;
            } else {
                TreeNode predecessor = node.left;
                while (predecessor.right != null && predecessor.right != node) {
                    predecessor = predecessor.right;
                }
                if (predecessor.right == null) {
                    predecessor.right = node;
                    node = node.left;
                } else {
                    predecessor.right = null;
                    traversal.add(node.val);
                    node = node.right;
                }
            }
        }
        return traversal;
    }
}

复杂度分析

  • 时间复杂度: O ( n ) O(n) O(n),其中 n n n 是二叉树的结点数。使用莫里斯遍历,每个结点最多被访问两次。

  • 空间复杂度: O ( 1 ) O(1) O(1)。注意返回值不计入空间复杂度。文章来源地址https://www.toymoban.com/news/detail-492084.html

到了这里,关于二叉树题目:二叉树的中序遍历的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包