日野弥生：勉強しよう
LeetCode 94 - 二叉树的中序遍历
发表于2025年02月14日
递归法可以无脑解决先序、中序、后序遍历。
class Solution {
private:
vector<int> m_result{};
public:
void preorderTraversalImpl(TreeNode* root)
{
if(!root)
return;
m_result.push_back(root->val);
preorderTraversalImpl(root->left);
preorderTraversalImpl(root->right);
}
vector<int> preorderTraversal(TreeNode* root) {
preorderTraversalImpl(root);
return m_result;
}
};python3版本如下，注意成员函数的调用方式。
class Solution:
def inorderTraversalImpl(self, root: Optional[TreeNode]):
if root is None:
return
if root.left is not None:
self.inorderTraversalImpl(root.left)
self.lst.append(root.val)
if root.right is not None:
self.inorderTraversalImpl(root.right)
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
self.lst = []
self.inorderTraversalImpl(root)
return self.lst非递归法也是利用栈结构模拟函数栈进行深度优先搜索。注意，此处和前序遍历的迭代版本不同的是，我们需要进栈的数据需要有一个标记值，标记当前结点是否需要处理右子树。
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
stack = deque()
result = []
while root is not None or stack:
if root is not None:
# 中序遍历最后处理右子树，所以右子树先进栈，标记值False也一同进栈，表达该右子树作为结点并没有遍历过
if root.right is not None:
stack.append([root.right, False])
# 根节点进栈，由于当前根节点的右子树已经在上面一行代码中进过栈，所以标记值为True
stack.append([root, True])
root = root.left
else:
# 左子树到底时出栈
item = stack.pop()
# 注意此处的key和value的获取方式
key = item[0]
value = item[1]
if value == False:
# 如果该节点没被标记，说明该节点应该被正常地进行迭代，即需要把当前结点和该节点的右子树进栈并继续遍历左子树
root = key
else:
# 如果已经被标记，说明右子树被遍历，此时只需直接记录结构并置空即可
result.append(key.val)
root = None
return result