一、题目描述(javascript解题)：

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

原题来源：leetCode：94题

示例描述：

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

示例2：

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

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

提示：

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

中序遍历方式：

二、递归解题

思路分析：

使用递归解题是该题最简单的解法，我写一个函数，传入需要遍历的二叉树的根节点，函数中判断root是否为空结点，是就直接返回一个空数组[],不是空结点就进行操作。操作中分为三部分，第一部分使其定位到最左下的结点(直到空)，开始第二部分，这时开始将此时root.val压入数组存储，进行第三部分，继续对右边进行同样的操作。在运行中三部分不停的操作，直到遍历到最右下叶子结点。

AC代码：

var inorderTraversal = function(root,array=[]) {
    if(root){
        inorderTraversal(root.left,array);//1
        array.push(root.val);//2
        inorderTraversal(root.right,array)//3
    }
    return array;
}

三、迭代解题

思路分析：

使用栈的方式对其操作,利用栈后进先出的特点对得到应有的遍历结果。

AC 代码：

var inorderTraversal = function(root){
    const stack=[];
    const result=[];
    while(root||stack.length>0){
        while(root){//双重循环找到最左叶子节点
            stack.push(root);
            root=root.left;
        }
        root=stack.pop();
        result.push(root.val);
        root=root.right;
    }
    return result;
}

四、总结：

第一次以文章形式总结刷的leetCode题目，可能总结的不到位，但是随着更多的文章的产出，一定会越来越完善。

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