当前位置：首页 > news >正文

第六章二叉树part01

news 2026/3/26 15:55:27

2026.02.07 第十一天

144 二叉树的前序遍历

二叉树基础

由于是前序遍历，把每一层递归需要处理的内容放在最前面即可~

class Solution {
private:void traversal(TreeNode* node, vector<int>& vec) {if(node == nullptr) {return;}vec.push_back(node->val);traversal(node->left, vec);traversal(node->right, vec);}
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> result;traversal(root, result);return result;}
};

迭代法实现：

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {if(root == nullptr) {return {};}vector<int> result;stack<TreeNode*> sta;sta.push(root);while(sta.empty() != true) {TreeNode* temp = sta.top();result.push_back(temp->val);sta.pop();if(temp->right != nullptr) {sta.push(temp->right);}if(temp->left != nullptr) {sta.push(temp->left);}}return result;}
};

144 二叉树的后序遍历

由于是后序遍历，把每一层递归需要处理的内容放在最后面即可~

class Solution {
private:void traversal(TreeNode* node, vector<int>& vec) {if(node == nullptr) {return;}traversal(node->left, vec);traversal(node->right, vec);vec.push_back(node->val);}public:vector<int> postorderTraversal(TreeNode* root) {vector<int> result;traversal(root, result);return result;}
};

迭代法实现：

很巧妙的思想，将left和right的入栈顺序反转，从而将数组中元素的顺序由中左右变成中右左，最后反转整个数组，得到左右中，也就是后序遍历结果。

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {if (root == nullptr) {return {};}vector<int> result;stack<TreeNode*> sta;sta.push(root);while (sta.empty() != true) {TreeNode* temp = sta.top();result.push_back(temp->val);sta.pop();if (temp->left != nullptr) {sta.push(temp->left);}if (temp->right != nullptr) {sta.push(temp->right);}}reverse(result.begin(), result.end());return result;}
};

144 二叉树的中序遍历

由于是中序遍历，把每一层递归需要处理的内容放在中间即可~

class Solution {
private:void traversal(TreeNode* node, vector<int>& vec) {if(node == nullptr) {return;}traversal(node->left, vec);vec.push_back(node->val);traversal(node->right, vec);}public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;traversal(root, result);return result;}
};

迭代法实现：

中序迭代相交前后稍微复杂了一些，需要专门定义一个指针来控制节点走向。

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;TreeNode* cur = root;while(cur != nullptr || !st.empty()) {if(cur != nullptr) {st.push(cur);cur = cur->left;}else {cur = st.top();st.pop();result.push_back(cur->val);cur = cur->right;}}return result;}
};