[LeetCode94题二叉树的中序遍历] | 刷题打卡

前言

在做题之前我们先来大概了解下二叉树的遍历方式。

为什么叫前序、后序、中序？

一棵二叉树由根结点、左子树和右子树三部分组成，若规定 D、L、R 分别代表遍历根结点、遍历左子树、遍历右子树，则二叉树的遍历方式有 6 种：DLR、DRL、LDR、LRD、RDL、RLD。由于先遍历左子树和先遍历右子树在算法设计上没有本质区别，所以，只讨论三种方式：

DLR--前序遍历（根在前，从左往右，一棵树的根永远在左子树前面，左子树又永远在右子树前面 ）

LDR--中序遍历（根在中，从左往右，一棵树的左子树永远在根前面，根永远在右子树前面）

LRD--后序遍历（根在后，从左往右，一棵树的左子树永远在右子树前面，右子树永远在根前面）

前序遍历

前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。

若二叉树为空则结束返回，否则：

• （1）访问根结点。
• （2）前序遍历左子树。
• （3）前序遍历右子树 。

需要注意的是：遍历左右子树时仍然采用前序遍历方法。 如图所示二叉树

前序遍历结果：ABDECF 已知后序遍历和中序遍历，就能确定前序遍历。

前序遍历

中序遍历

中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。若二叉树为空则结束返回，否则：

• （1）中序遍历左子树

• （2）访问根结点

• （3）中序遍历右子树

如图所示二叉树，中序遍历结果：DBEAFC

中序遍历

后序遍历

后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。即：

若二叉树为空则结束返回，否则：

• （1）后序遍历左子树
• （2）后序遍历右子树
• （3）访问根结点

如图所示二叉树 后序遍历结果：DEBFCA 已知前序遍历和中序遍历，就能确定后序遍历

后序遍历

题目介绍

题目地址: 94. 二叉树的中序遍历

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

示例 1：

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

示例 2：

输入：root = []
输出：[]

示例 3：

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

示例 4：

输入：root = [1,2]
输出：[2,1]

示例 5：

输入：root = [1,null,2]
输出：[1,2]

提示：

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

解题思路

题目要求返回给定二叉树root的中序遍历，根据前言中的关于中序遍历的描述，这道题的解法我们就按照这样的顺序来。

我们用递归函数inOrder来模拟二叉树遍历的过程。

根据上文中的定义，我们解题步骤如下：

• 递归调用 inOrder(root.left) 来遍历 root 节点的左子树
• 然后root 节点的值val加入答案
• 再递归调用inOrder(root.right) 来遍历 root 节点的右子树即可。

解题代码

var inorderTraversal = function(root) {
    const res = []
    const inOrder = (root) => {
        if (!root) {
            return;
        }
        inOrder(root.left);
        res.push(root.val);
        inOrder(root.right);
    }
    inOrder(root);
    return res;
};

刷题打卡记录

这里是之前的刷题打卡记录，大家有兴趣的可以看下，如果有什么不同的见解和看法或者觉得有什么错误的，欢迎在评论区留言！???

[LeetCode0303题区域和检索 - 数组不可变] | 刷题打卡

[LeetCode1200. 最小绝对差] | 刷题打卡

[LeetCode0304题二维区域和检索 - 矩阵不可变] | 刷题打卡

[LeetCode11题盛最多水的容器] | 刷题打卡

[LeetCode0338题比特位计数] | 刷题打卡

[LeetCode209题长度最小的子数组] | 刷题打卡

[LeetCode236题二叉树的最近公共祖先] | 刷题打卡

[LeetCode141题环形链表] | 刷题打卡

[LeetCode53题最大子序和] | 刷题打卡

[LeetCode48题旋转图像] | 刷题打卡

[LeetCode155题最小栈] | 刷题打卡

[LeetCode1124题表现良好的最长时间段] | 刷题打卡

[LeetCode274题H指数] | 刷题打卡

[LeetCode367题有效的完全平方数] | 刷题打卡

[LeetCode1047题删除字符串中的所有相邻重复项] | 刷题打卡

[LeetCode160题相交链表] | 刷题打卡

[LeetCode1438题绝对差不超过限制的最长连续子数组] | 刷题打卡

[LeetCode434题字符串中的单词数] | 刷题打卡

[LeetCode75题颜色分类] | 刷题打卡

[LeetCode513题找树左下角的值] | 刷题打卡

总结

加油！hxdm！！！???

本文正在参与「掘金 2021 春招闯关活动」, 点击查看 活动详情