LeetCode 94. 二叉树的中序遍历

题目描述

🔥 94. 二叉树的中序遍历

image-20230305164849556

思路分析

递归

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

func inorderTraversal(root *TreeNode) []int {
	var res []int         // 用于存储遍历结果的切片
	var stack []*TreeNode // 栈用于辅助遍历
	cur := root           // 从根节点开始遍历
	for cur != nil || len(stack) > 0 {
		// 将左子树的所有左节点入栈
		for cur != nil {
			stack = append(stack, cur)
			cur = cur.Left
		}
		// 弹出栈顶节点并将其值加入结果切片
		cur = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		res = append(res, cur.Val)
		// 遍历右子树
		cur = cur.Right
	}
	return res
}

🍏 点击查看 Java 题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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

相似题目

题目 难度 题解
验证二叉搜索树 Medium  
二叉树的前序遍历 Easy  
二叉树的后序遍历 Easy  
二叉搜索树迭代器 Medium  
二叉搜索树中第 K 小的元素 Medium  
最接近的二叉搜索树值 II Hard  
二叉搜索树中的中序后继 Medium  
将二叉搜索树转化为排序的双向链表 Medium  
二叉搜索树节点最小距离 Easy  
本文作者:
本文链接: https://hgnulb.github.io/blog/62975418
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！