?算法OJ?二叉樹的中序遍歷【樹的遍歷】（C++實現）Binary Tree Inorder Traversal
Given the root of a binary tree, return the preorder traversal of its nodes’ values.

Example 1:

Input: root = [1,null,2,3]
Output: [1,2,3]

Explanation:

Example 2:

Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output: [1,2,4,5,6,7,3,8,9]

Explanation:

Example 3:

Input: root = []
Output: []

Example 4:

Input: root = [1]
Output: [1]

// 定義二叉樹節點結構
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

遞歸解法

• 前序遍歷的順序是：$根節點\to 左子樹\to 右子樹$。
• 使用遞歸實現。

#include <vector>
using namespace std;// 遞歸前序遍歷函數
void preorderTraversalHelper(TreeNode* root, vector<int>& result) {if (root == NULL) {return;}// 訪問根節點result.push_back(root->val);// 遞歸遍歷左子樹preorderTraversalHelper(root->left, result);// 遞歸遍歷右子樹preorderTraversalHelper(root->right, result);
}// 前序遍歷主函數
vector<int> preorderTraversal(TreeNode* root) {vector<int> result;preorderTraversalHelper(root, result);return result;
}

迭代解法（使用棧）

使用 棧 來模擬遞歸過程。以下是迭代方法的實現：

#include <vector>
#include <stack>
using namespace std;// 迭代前序遍歷函數
vector<int> preorderTraversal(TreeNode* root) {vector<int> result;if (root == NULL) {return result;}stack<TreeNode*> stack;stack.push(root);while (!stack.empty()) {TreeNode* node = stack.top();stack.pop();result.push_back(node->val);// 先將右子節點壓棧，再壓左子節點if (node->right != NULL) {stack.push(node->right);}if (node->left != NULL) {stack.push(node->left);}}return result;
}