LeetCode 94. Binary Tree Inorder Traversal
Given the root
of a binary tree, return the inorder traversal
of its nodes’ values.
method
中序遍历:左-根-右
- 递归
void inorder(TreeNode* cur, vector<int>& ret) {
if (cur == nullptr) return;
inorder(cur->left, ret);
ret.push_back(cur->val);
inorder(cur->right, ret);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ret;
inorder(root, ret);
return ret;
}
- 迭代
- 一直往左子树深度遍历,期间把元素插入栈中,直到空
空的话说明到了无左子树的节点,开始弹出元素,同时查看是否有右节点 - 有右节点,返回步骤1
- 无右节点,继续弹出元素
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ret;
if (!root) return ret;
stack<TreeNode*> st;
TreeNode* cur = root;
while (cur || !st.empty()) {
if (cur) {
st.push(cur);
cur = cur->left;
}
else { // cur空,但栈里有元素,就要弹出
cur = st.top();
st.pop();
ret.push_back(cur->val);
cur = cur->right;
}
}
return ret;
}
LeetCode 144. Binary Tree Preorder Traversal
Given the root
of a binary tree, return the preorder traversal
of its nodes’ values.
method
前序遍历:根-左-右
- 递归法
void preorder(TreeNode* cur, vector<int>& ret) {
if (cur == nullptr) return;
ret.push_back(cur->val);
preorder(cur->left, ret);
preorder(cur->right, ret);
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ret;
preorder(root, ret);
return ret;
}
- 迭代法
先放右节点,再放左节点,待会取的时候就是先左再右
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ret;
if (!root) return ret;
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
TreeNode* cur = st.top();
st.pop();
ret.push_back(cur->val);
if (cur->right) st.push(cur->right);
if (cur->left) st.push(cur->left);
}
return ret;
}
LeetCode 145. Binary Tree Postorder Traversal
Given the root
of a binary tree, return the postorder traversal
of its nodes’ values.
method
后序遍历:左-右-根
- 递归法
void postorder(TreeNode* cur, vector<int>& ret) {
if (cur == nullptr) return;
postorder(cur->left, ret);
postorder(cur->right, ret);
ret.push_back(cur->val);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ret;
postOrder(root, ret);
return ret;
}
- 迭代法
后序左右根,反过来就是根右左,与先序遍历差不多,最后反转就可以了
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ret;
if (root == nullptr) return ret;
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
TreeNode* cur = st.top();
st.pop();
ret.push_back(cur->val);
if (cur->left) st.push(cur->left);
if (cur->right) st.push(cur->right);
}
reverse(ret.begin(), ret.end());
return ret;
}