日野弥生：勉強しよう
LeetCode 144 - 二叉树的前序遍历
发表于2025年02月13日
递归法可以无脑解决先序、中序、后序遍历。
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;
}
};迭代法解决该问题时，总体的思想都是利用栈数据结构来模拟实际递归的函数栈空间，从而实现在非递归的情况下模拟递归。
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
result = []
stack = deque()
while root is not None or stack:
if root is not None:
# 先根遍历，先处理根节点后把右子结点放入栈内
result.append(root.val)
if root.right is not None:
stack.append(root.right)
root = root.left
elif stack:
# 当左子树到底时，从栈内依次出栈处理各层的右子树
root = stack.pop()
return result