day14 - 二叉树part01
力扣144. 二叉树的前序遍历
最基本的递归调用，递推三个关键
- 参数和返回值
- 终止条件
- 每一层的逻辑
代码：
递归法
class Solution {
public:
vector<int> result;
void traverse(TreeNode* root)
{
if (root == nullptr)
{
return;
}
result.push_back(root->val);
traverse(root->left);
traverse(root->right);
}
vector<int> preorderTraversal(TreeNode* root) {
traverse(root);
return result;
}
};
后序遍历和中序遍历同理，只是每层逻辑那三行代码顺序不同。
迭代法
用一个栈来接收节点，首先把根节点压栈，然后如果栈不是空的，把栈顶元素的值放进结果集，然后出栈，如果栈顶元素的左右孩子不是空，就压栈，然后继续循环。注意，如果是前序遍历，根左右的方式，压栈就要先压右孩子，再压左孩子。这样先弹出来的才是左孩子。
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> result;
if (root == NULL) return result;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top(); // 中
st.pop();
result.push_back(node->val);
if (node->right) st.push(node->right); // 右（空节点不入栈）
if (node->left) st.push(node->left); // 左（空节点不入栈）
}
return result;
}
};
中序遍历
迭代法不能再使用和前序遍历一样的套路。
因为前序遍历是，先把父节点压栈，然后弹出父节点，并压入左右孩子节点。
但是中序遍历不同，逻辑是，用一个cur节点进行遍历，一路把左孩子全部压栈，然后如果左孩子是空了，那么左就结束了，让cur指向栈顶，并pop掉栈顶元素，也就是根节点，然后把cur指向右孩子。此时如果有右孩子，那么继续压栈右孩子的左孩子，如果没有，cur指向栈顶元素。
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
if (root == NULL) return 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;
}
};
后序遍历
在前序遍历的基础上修改，因为前序遍历是中右左处理顺序，弹出来是中左右。那么改为中左右，弹出来是中右左，再翻转结果，得到左右中。
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
if (root == NULL) return result;
stack<TreeNode*> st;
st.push(root);
while (!st.empty())
{
TreeNode* node = st.top();
st.pop();
result.push_back(node->val);
if (node->left) st.push(node->left);
if (node->right) st.push(node->right);
}
reverse(result.begin(), result.end());
return result;
}
};