随想录二刷Day15——二叉树

二叉树

2. 递归遍历二叉树

144. 二叉树的前序遍历

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

94. 二叉树的中序遍历

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

145. 二叉树的后序遍历

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

3. 二叉树的迭代遍历

144. 二叉树的前序遍历

遍历顺序：中左右
压栈顺序：中（直接弹出）右左

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> result;if (root == NULL) return result;stack<TreeNode *> stk;stk.push(root);while ( !stk.empty() ) {TreeNode *cur = stk.top();stk.pop();result.push_back(cur->val); // 中if (cur->right) stk.push(cur->right); // 右if (cur->left) stk.push(cur->left); // 左}return result;}
};

145. 二叉树的后序遍历

先序遍历：中左右
后序遍历：左右中
所以把先序遍历的压栈顺序修改，得到遍历 中右左 的顺序，然后翻转遍历结果。

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> result;if (root == NULL) return result;stack<TreeNode *> stk;stk.push(root);while ( !stk.empty() ) {TreeNode *cur = stk.top();stk.pop();result.push_back(cur->val); // 中if (cur->left) stk.push(cur->left); // 左if (cur->right) stk.push(cur->right); // 右}reverse(result.begin(), result.end()); // 此时遍历顺序为 中右左，翻转得到后序遍历的结果return result;}
};

94. 二叉树的中序遍历

中序遍历不太一样，要借助指针查看左子节点是否为空，来得到左中右的遍历结果

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode *> stk;TreeNode *cur = root;while ( cur != NULL || !stk.empty() ) {if (cur != NULL) { // 如果当前节点不空，则一直找左子节点stk.push(cur);cur = cur->left;} else {cur = stk.top(); // 上个节点的左节点已经找完了stk.pop();result.push_back(cur->val); // 左完了该中cur = cur->right; // 中完了去看右子树}}return result;}
};

4. 二叉树的统一迭代法

统一遍历方式，按遍历顺序的逆序输出结果。

144. 二叉树的前序遍历

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode *> stk;if (root) stk.push(root);while ( !stk.empty() ) {TreeNode *cur = stk.top();stk.pop();if (cur) { // 遇到 null 说明是待处理节点if (cur->right) stk.push(cur->right); // 右if (cur->left) stk.push(cur->left); // 左stk.push(cur); // 中stk.push(NULL); // 标记节点} else { // 遇到 NULL 标记，开始处理节点cur = stk.top(); // 取出被标记的待处理节点result.push_back(cur->val);stk.pop();}}return result;}
};

94. 二叉树的中序遍历

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode *> stk;if (root) stk.push(root);while ( !stk.empty() ) {TreeNode *cur = stk.top();stk.pop();if (cur) {if (cur->right) stk.push(cur->right); // 右stk.push(cur); // 中stk.push(NULL); // 标记if (cur->left) stk.push(cur->left); // 左} else {cur = stk.top();result.push_back(cur->val);stk.pop();}}return result;}
};

145. 二叉树的后序遍历

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