LeetCode-热题100：94. 二叉树的中序遍历

题目描述

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

代码及注释

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func inorderTraversal(root *TreeNode) []int {
    var res []int           // 用于存储遍历结果
    var stack []*TreeNode   // 用于模拟栈的数据结构，存储遍历过程中的节点

    // 循环条件，当栈不为空或当前节点不为空时，继续遍历
    for len(stack) > 0 || root != nil {
        // 先将左子树全部入栈
        for root != nil {
            stack = append(stack, root)
            root = root.Left
        }
        
        // 当左子树遍历完成后，取出栈顶节点，记录其值，并将其右子树作为当前节点进行遍历
        root = stack[len(stack) - 1]
        stack = stack[:len(stack) - 1]
        res = append(res, root.Val)
        root = root.Right
    }
    return res
}

代码解释

1. 变量定义:

   var res []int           // 用于存储遍历结果
   var stack []*TreeNode   // 用于模拟栈的数据结构，存储遍历过程中的节点
   

   • res：用于存储遍历结果的切片。
   • stack：模拟栈的切片，用于存储遍历过程中的节点。

2. 循环遍历:

   for len(stack) > 0 || root != nil {
       // 先将左子树全部入栈
       for root != nil {
           stack = append(stack, root)
           root = root.Left
       }
       
       // 当左子树遍历完成后，取出栈顶节点，记录其值，并将其右子树作为当前节点进行遍历
       root = stack[len(stack) - 1]
       stack = stack[:len(stack) - 1]
       res = append(res, root.Val)
       root = root.Right
   }
   

   • 当栈不为空或当前节点不为空时，循环进行遍历。
   • 先将当前节点及其所有左子节点入栈。
   • 当左子树遍历完成后，从栈中取出栈顶节点，记录其值，并将其右子树作为当前节点进行遍历。

这个非递归的中序遍历使用了栈来模拟递归调用的过程，时间复杂度为 O(n)，其中 n是二叉树的节点数。