Leetcode 94,144,145:二叉树的前序，中序，后序遍历
Leetcode 94,144,145:二叉树的前序，中序，后序遍历
前序遍历：
144. 二叉树的前序遍历
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
输入：root = [1,null,2,3]输出：[1,2,3]解释：
示例 2：
输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]输出：[1,2,4,5,6,7,3,8,9]解释：
示例 3：
输入：root = []输出：[]示例 4：
输入：root = [1]输出：[1]提示：
- 树中节点数目在范围
[0, 100]内 -100 <= Node.val <= 100
访问顺序： 根节点 -> 左子树 -> 右子树
递归实现：
class Solution {public: vector preorderTraversal(TreeNode* root) { vector result; preorder(root, result); return result; } private: void preorder(TreeNode* node, vector& result) { if (!node) return; result.push_back(node->val); // 先访问根节点 preorder(node->left, result); // 再访问左子树 preorder(node->right, result); // 最后访问右子树 }};非递归实现（用栈）：
class Solution {public: vector preorderTraversal(TreeNode* root) { vector result; if (!root) return result; stack stk; stk.push(root); while (!stk.empty()) { TreeNode* node = stk.top(); stk.pop(); result.push_back(node->val); // 访问当前节点 // 先右后左，保证左子树先被处理 if (node->right) stk.push(node->right); if (node->left) stk.push(node->left); } return result; }};中序遍历
94. 二叉树的中序遍历
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
输入：root = [1,null,2,3]输出：[1,3,2]示例 2：
输入：root = []输出：[]示例 3：
输入：root = [1]输出：[1]提示：
- 树中节点数目在范围
[0, 100]内 -100 <= Node.val <= 100
访问顺序： 左子树 -> 根节点 -> 右子树
递归实现：
class Solution {public: vector inorderTraversal(TreeNode* root) { vector result; inorder(root, result); return result; } private: void inorder(TreeNode* node, vector& result) { if (!node) return; inorder(node->left, result); // 先访问左子树 result.push_back(node->val); // 然后访问根节点 inorder(node->right, result); // 最后访问右子树 }};非递归实现（用栈）：
class Solution {public: vector inorderTraversal(TreeNode* root) { vector result; stack stk; TreeNode* current = root; while (current || !stk.empty()) { while (current) { // 一路向左 stk.push(current); current = current->left; } current = stk.top(); stk.pop(); result.push_back(current->val); // 访问当前节点 current = current->right; // 处理右子树 } return result; }};后序遍历
145. 二叉树的后序遍历
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
示例 1：
输入：root = [1,null,2,3]输出：[3,2,1]解释：
示例 2：
输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]输出：[4,6,7,5,2,9,8,3,1]解释：
示例 3：
输入：root = []输出：[]示例 4：
输入：root = [1]输出：[1]提示：
- 树中节点的数目在范围
[0, 100]内 -100 <= Node.val <= 100
访问顺序： 左子树 -> 右子树 -> 根节点
递归实现：
class Solution {public: vector postorderTraversal(TreeNode* root) { vector result; postorder(root, result); return result; } private: void postorder(TreeNode* node, vector& result) { if (!node) return; postorder(node->left, result); // 先访问左子树 postorder(node->right, result); // 再访问右子树 result.push_back(node->val); // 最后访问根节点 }};非递归实现：
class Solution {public: vector postorderTraversal(TreeNode* root) { vector result; if (!root) return result; stack stk; stk.push(root); while (!stk.empty()) { TreeNode* node = stk.top(); stk.pop(); result.push_back(node->val); // 先把根节点放进去 // 先左后右，保证右子树先被处理 if (node->left) stk.push(node->left); if (node->right) stk.push(node->right); } reverse(result.begin(), result.end()); // 翻转得到后序 return result; }};
