代碼解決

這段代碼實現了二叉樹的前序遍歷，前序遍歷的順序是：訪問根節點 -> 遞歸遍歷左子樹 -> 遞歸遍歷右子樹。以下是詳細解釋，包括各個部分的注釋：

// 二叉樹節點的定義
struct TreeNode {int val;                // 節點值TreeNode *left;         // 左子節點TreeNode *right;        // 右子節點TreeNode() : val(0), left(nullptr), right(nullptr) {}                      // 默認構造函數TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}                 // 帶值的構造函數TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} // 帶值和左右子節點的構造函數
};class Solution {
public:// 遞歸遍歷函數，用于前序遍歷void traversal(TreeNode* tree, vector<int>& res){if(tree == NULL) return;            // 如果節點為空，則直接返回res.push_back(tree->val);           // 訪問根節點，將節點值加入結果向量traversal(tree->left, res);         // 遞歸遍歷左子樹traversal(tree->right, res);        // 遞歸遍歷右子樹}// 前序遍歷的主函數vector<int> preorderTraversal(TreeNode* root) {vector<int> result;                 // 存儲遍歷結果的向量traversal(root, result);            // 調用遞歸函數進行前序遍歷return result;                      // 返回結果向量}
};

詳細解釋

1. TreeNode 結構體：

   • 定義了一個二叉樹節點結構體TreeNode，包括節點的值val，左子節點指針left，和右子節點指針right。
   • 提供了三種構造函數：
     • 默認構造函數初始化節點值為0，左右子節點為空。
     • 帶一個整數參數的構造函數初始化節點值為給定值，左右子節點為空。
     • 帶一個整數和兩個子節點參數的構造函數初始化節點值和左右子節點。

2. Solution 類：

   • 包含前序遍歷二叉樹的實現。

3. traversal 函數：

   • 這是一個遞歸函數，用于執行前序遍歷。
   • 參數tree是當前節點，res是存儲遍歷結果的向量。
   • 首先檢查當前節點是否為空，如果為空，則返回。
   • 然后將當前節點的值加入結果向量。
   • 接下來遞歸遍歷左子樹和右子樹。

4. preorderTraversal 函數：

   • 這是前序遍歷的主函數。
   • 創建一個空的結果向量result。
   • 調用遞歸函數traversal從根節點開始進行前序遍歷。
   • 最后返回結果向量。

前序遍歷的順序

在前序遍歷中，首先訪問根節點，然后遞歸遍歷左子樹，最后遞歸遍歷右子樹。例如，給定以下二叉樹：

使用場景

前序遍歷常用于：

• 復制二叉樹
• 計算二叉樹節點的數量
• 前序表達式的求值
• 將二叉樹轉換為其他數據結構