LeetCode 之 JavaScript 解答第94题 —— 二叉树的中序遍历

Jason 发布于2019-08-23 17:19 / 856人阅读

摘要：小鹿题目二叉树中序遍历给定一个二叉树，返回它的中序遍历。通常递归的方法解决二叉树的遍历最方便不过，但是我还是喜欢增加点难度，用一般的迭代循环来实现。

Time：2019/4/25
Title:Binary Tree Inorder Traversal
Difficulty: Medium
Author:小鹿

题目：Binary Tree Inorder Traversal（二叉树中序遍历）

Given a binary tree, return the inorder traversal of its nodes" values.

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

Example:

Input: [1,null,2,3]
   1
    
     2
    /
   3

Output: [1,3,2]

Follow up: Recursive solution is trivial, could you do it iteratively?

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

solve:

▉ 问题分析

1）二叉树的前、中、后遍历，首先明白前、中、后遍历的顺序是什么，对于二叉树的中序遍历来说，顺序是左子树节点 —> 根节点 —> 右子树节点。

2）通常递归的方法解决二叉树的遍历最方便不过，但是我还是喜欢增加点难度，用一般的迭代循环来实现。

▉ 算法思路

递归法：

1）判断当前树是否为空。

2）递归树的左子树结点。

3）输出当前结点的值。

4）递归树的右子树节点。

迭代循环法：

1）声明一个栈，将树的左子节点入栈。

2）每出栈一个结点，输出当前结点的值，且将该结点的右子树进行遍历打印，保证每个出栈的结点输出值之后，再输出上一个左子节点之前，将当前结点的右子节点遍历毕。

3）整棵树遍历完毕的终止条件就是当前栈是否存在结点（树的左子节点）。

▉ 递归实现

var inorderTraversal = function(root) {
    let arr = []
    const inorder = root =>{
        // 判断当前的结点是否为空
        if(root == null) return null;
        // 递归左子树
        inorder(root.left)
        // 输出结点值
        arr.push(root.val)
        // 递归右子树
        inorder(root.right)
    }
    inorder(root)
    return arr
};

▉ 迭代实现

// 迭代实现二叉树的中序遍历
var inorderTraversal = function(root) {
    let stack = [];
    let result = [];

    while(true){
        // 判断树是否为空
        if(root == null) return result;

        // 先将树的左子节点推入栈中
        while(root !== null){
            stack.push(root);
            root = root.left;
        }

        // 遍历的终止条件
        if(stack.length !== 0){
            // 输出栈中的结点
            let temp = stack.pop();
            result.push(temp.val);
            // 如果当前存在右子节点，要先打印右子树节点
            root = temp.right;
        }else{
            break;
        }
    }
    return result;
}

▉ 举一反三

1）试着分别写出前序遍历、后序遍历的递归实现和迭代实现代码。

欢迎一起加入到 LeetCode 开源 Github 仓库，可以向 me 提交您其他语言的代码。在仓库上坚持和小伙伴们一起打卡，共同完善我们的开源小仓库！
Github：https://github.com/luxiangqia...
欢迎关注我个人公众号：「一个不甘平凡的码农」，记录了自己一路自学编程的故事。

服务器托管超融合服务器二叉树的遍历二叉树的存储二叉树的存储结构 java二叉树的构建

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/104155.html

LeetCode 之 JavaScript 解答第98题 —— 验证二叉搜索树

摘要：小鹿题目验证二叉搜索树给定一个二叉树，判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征节点的左子树只包含小于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。算法思路定义全局的变量，用来返回是否为二叉搜索树。 Time：2019/4/24Title: Vaildata Binary Search TreeDifficulty: MediumAuthor: 小鹿 ...

用户84 2019-08-23 17:12 评论0 收藏0
【LeetCode 二叉树专项】二叉搜索树中的中序后继（285）

摘要：解法二迭代中序遍历分析作者二叉搜索树的中序后继是中序遍历中当前节点之后最小的节点。文章目录 1. 题目1.1 示例1.2 说明1.3 限制 2....

ccj659 2021-11-24 09:39 评论0 收藏0
算法之不定期更新（四）—— 从前序与中序遍历序列构造二叉树（2018-06-02）

摘要：树的前序，中序遍历的结构如下图可以看出，通过前序遍历可以确定根节点，再通过中序遍历和根节点的位置可以确定出左子树和右子树。另外左子树的前序遍历和中序遍历的顺序跟在其父树中的顺序一样。因此可以确定有一种递归解法。从前序与中序遍历序列构造二叉树今天带来的是Leetcode上的一个经典题：从前序与中序遍历序列构造二叉树原题干： /** Definition for a binary ...

charles_paul 2019-08-26 11:57 评论0 收藏0