【重点非递归版】【二叉树】94.二叉树的中序遍历-CSDN博客

本文链接：https://blog.csdn.net/Allenlzcoder/article/details/134805300

本文介绍了两种方法实现二叉树的中序遍历：迭代版通过栈结构逐步遍历节点，而递归版则是通过函数调用实现。详细展示了如何在Solution类中分别使用这两种方法处理TreeNoderoot节点。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目
重点掌握迭代版遍历

Python

递归版

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = list()
        if root == None:
            return list()
        if root.left:
            res.extend(self.inorderTraversal(root.left))
        res.append(root.val)
        if root.right:
            res.extend(self.inorderTraversal(root.right))

        return res

迭代版

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = list()
        VISITED, NO_VISITED = 1, 0
        stack = [(NO_VISITED, root)]
        while stack:
            color, node = stack.pop()
            if not node:
                continue
            if color == NO_VISITED:
                stack.append((NO_VISITED, node.right))
                stack.append((VISITED, node))
                stack.append((NO_VISITED, node.left))
            else:
                res.append(node.val)
        return res

Java

法1：迭代版遍历

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

        return res;
    }
}

法2：递归版遍历

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        fun(root, res);
        return res;
    }

    public void fun(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        fun(root.left, res);
        res.add(root.val);
        fun(root.right, res);
    }
}