144. 二叉树的前序遍历
题目：
给定一个二叉树，返回它的 前序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,2,3]
解法1：递归
class Solution {
private:
void takeVal(TreeNode *root, vector<int>& res) {
if (NULL == root)
return;
res.push_back(root->val);
takeVal(root->left, res);
takeVal(root->right, res);
}
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
if (NULL == root)
return res;
takeVal(root, res);
return res;
}
};
解法2：用栈，先入右子树，再入左子树
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
if (NULL == root)
return res;
stack<TreeNode*> sta;
TreeNode* node;
sta.push(root);
while (!sta.empty()) {
node = sta.top();
sta.pop();
res.push_back(node->val);
if (node->right)
sta.push(node->right);
if (node->left)
sta.push(node->left);
}
return res;
}
};
解法3：用栈，只压右子树
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
if (NULL == root)
return res;
stack<TreeNode*> sta;
TreeNode* node = root;
while (true) {
if (node) {
res.push_back(node->val);
if (node->right)
sta.push(node->right);
node = node->left;
} else {
if (sta.empty())
break;
node = sta.top();
sta.pop();
}
}
return res;
}
};
145. 二叉树的后序遍历
题目：
给定一个二叉树，返回它的 后序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [3,2,1]
解法1：递归
class Solution {
private:
void takeVal(TreeNode *root, vector<int>& res) {
if (NULL == root)
return;
takeVal(root->left, res);
takeVal(root->right, res);
res.push_back(root->val);
}
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
if (NULL == root)
return res;
takeVal(root, res);
return res;
}
};
解法2：用栈压入左右子节点
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
if (NULL == root)
return res;
stack<TreeNode*> sta;
TreeNode* node;
sta.push(root);
while (!sta.empty()) {
node = sta.top();
root = node; //在处理其子节点前，记住这个节点
while (node->left) { //处理左子树
node = node->left;
root->left = NULL; //节点左指针剪枝，避免无限重复访问
sta.push(node);
root =node;
}
if (root->right) { //转向右子树，重复处理其左子树
node = root->right;
root->right = NULL; //节点右指针剪枝
sta.push(node);
root = node;
} else { //没有左子树，没有右子树，即压入节点
res.push_back(root->val);
sta.pop();
}
}
return res;
}
};
这种解法调用后，会修改树结构，即将树拆成了一个个节点。
解法3：用栈压入左右子节点，用辅助标记节点隔开父子节点，不修改原树
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
if (NULL == root)
return res;
stack<TreeNode*> sta;
TreeNode* node;
sta.push(root);
while (!sta.empty()) {
node = sta.top();
if (node) { //父节点是栈的top()
sta.push(NULL); //在父节点和其孩子节点之间加一个标记
if (node->right)
sta.push(node->right);
if (node->left)
sta.push(node->left);
} else {
sta.pop(); //弹出标记的空节点
node = sta.top();
sta.pop();
res.push_back(node->val);
}
}
return res;
}
};
解法4：在解法3的基础上，做出可以前中后序遍历的模板
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
if (NULL == root)
return res;
stack<TreeNode*> sta;
TreeNode* node;
sta.push(root);
while (!sta.empty()) {
node = sta.top();
sta.pop(); //弹出该节点
if (node) {
sta.push(node); //先压入该父节点
sta.push(NULL);
if (node->right)
sta.push(node->right);
if (node->left)
sta.push(node->left);
} else { //标记节点已弹出
node = sta.top();
sta.pop();
res.push_back(node->val);
}
}
return res;
}
};
通过对当前父节点的弹出弹入，更改了父节点和其孩子节点的相对位置。这种解法稍微修改下if (node)中语句的相互顺序，可以实现前序，中序和后序遍历。
修改if (node)，最后压入父节点，得到该模板下的前序遍历，具体程序如下：
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
if (NULL == root)
return res;
stack<TreeNode*> sta;
TreeNode* node;
sta.push(root);
while (!sta.empty()) {
node = sta.top();
sta.pop();
if (node) {
if (node->right)
sta.push(node->right);
if (node->left)
sta.push(node->left);
sta.push(node); //最后压入父节点
sta.push(NULL);
} else {
node = sta.top();
sta.pop();
res.push_back(node->val);
}
}
return res;
}
};
修改if (node)，中间压入父节点，得到该模板下的中序遍历，具体程序如下：
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
if (NULL == root)
return res;
stack<TreeNode*> sta;
TreeNode* node;
sta.push(root);
while (!sta.empty()) {
node = sta.top();
sta.pop();
if (node) {
if (node->right)
sta.push(node->right);
sta.push(node); //中间压入父节点
sta.push(NULL);
if (node->left)
sta.push(node->left);
} else {
node = sta.top();
sta.pop();
res.push_back(node->val);
}
}
return res;
}
};
94. 二叉树的中序遍历
题目：
给定一个二叉树，返回它的中序 遍历。
解法1：递归
class Solution {
private:
void inorderRes(TreeNode *root, vector<int> &res) {
if (NULL == root)
return;
if (root->left)
inorderRes(root->left, res);
res.push_back(root->val);
if (root->right)
inorderRes(root->right, res);
}
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
if (NULL == root)
return res;
inorderRes(root, res);
return res;
}
};
解法2：用空指针做父节点后标记
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
if (NULL == root)
return res;
stack<TreeNode*> sta;
sta.push(root);
TreeNode *node;
while (!sta.empty()) {
node = sta.top();
sta.pop();
if (node) {
if (node->right)
sta.push(node->right);
sta.push(node);
sta.push(NULL);
if (node->left)
sta.push(node->left);
} else {
node = sta.top();
sta.pop();
res.push_back(node->val);
}
}
return res;
}
};
解法3：用栈一直压入从根开始的右子树，中序遍历输出
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
if (NULL == root)
return res;
stack<TreeNode*> sta;
TreeNode *node = root;
while (node || !sta.empty()) {
while (node) {
sta.push(node);
node = node->left;
}
node = sta.top();
sta.pop();
res.push_back(node->val);
node = node->right;
}
return res;
}
};
