理论基础
满二叉树:如果一棵二叉树只有度为0的结点和度为2的结点,且度为0的结点在同一层上,则这颗二叉树为满二叉树。
完全二叉树:在完全二叉树中,除了最底层结点可能没有填满外,其余每层节点数都达到最大值,并且最下面一层的结点都集中在该层最左边的若干位置。
二叉搜索树:二叉搜索树是一个有数值的有序树。
- 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
- 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
- 它的左、右子树也分别为二叉排序树
平衡二叉搜索树(AVL树):它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉搜索树。
LeetCode144. 二叉树的前序遍历
题目链接:144. 二叉树的前序遍历
初次尝试
抱着赶时间和学习的态度,直接看题解
看完代码随想录后的想法
递归法实现
class Solution {
public:
void Traversal(TreeNode* root, vector<int>& ans) {
if (root == NULL) return;
ans.push_back(root -> val);
Traversal(root -> left, ans);
Traversal(root -> right, ans);
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
Traversal(root, ans);
return ans;
}
};
迭代法实现(注意空结点不入栈)
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> ans;
if (root == NULL) return ans;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
st.pop();
ans.push_back(node -> val);
if (node -> right) st.push(node -> right);
if (node -> left) st.push(node -> left);
}
return ans;
}
};
统一迭代法(用NULL
作为标记)
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> ans;
if (root != NULL) st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
if (node != NULL) {
st.pop();
if (node -> right) st.push(node -> right);
if (node -> left) st.push(node -> left);
st.push(node);
st.push(NULL);
}
else {
st.pop();
node = st.top();
ans.push_back(node -> val);
st.pop();
}
}
return ans;
}
};
LeetCode145. 二叉树的后序遍历
题目链接:145. 二叉树的后序遍历
初次尝试
抱着赶时间和学习的态度,直接看题解
看完代码随想录后的想法
递归法实现
class Solution {
public:
void Traversal(TreeNode* root, vector<int>& ans) {
if (root == NULL) return;
Traversal(root -> left, ans);
Traversal(root -> right, ans);
ans.push_back(root -> val);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
Traversal(root, ans);
return ans;
}
};
迭代法实现(中左右 -> 中右左 -> 左右中)
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> ans;
if (root == NULL) return ans;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
st.pop();
ans.push_back(node -> val);
if (node -> left) st.push(node -> left);
if (node -> right) st.push(node -> right);
}
reverse(ans.begin(), ans.end());
return ans;
}
};
统一迭代法(用NULL
作为标记)
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> ans;
if (root != NULL) st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
if (node != NULL) {
st.pop();
st.push(node);
st.push(NULL);
if (node -> right) st.push(node -> right);
if (node -> left) st.push(node -> left);
}
else {
st.pop();
node = st.top();
ans.push_back(node -> val);
st.pop();
}
}
return ans;
}
};
LeetCode94. 二叉树的中序遍历
题目链接:94. 二叉树的中序遍历
初次尝试
抱着赶时间和学习的态度,直接看题解
看完代码随想录后的想法
递归法实现
class Solution {
public:
void Traversal(TreeNode* root, vector<int>& ans) {
if (root == NULL) return;
Traversal(root -> left, ans);
ans.push_back(root -> val);
Traversal(root -> right, ans);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
Traversal(root, ans);
return ans;
}
};
迭代法实现(借助指针)
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> ans;
TreeNode* cur = root;
while (cur != NULL || !st.empty()) {
if (cur != NULL) {
st.push(cur);
cur = cur -> left;
}
else {
cur = st.top();
st.pop();
ans.push_back(cur -> val);
cur = cur -> right;
}
}
return ans;
}
};
统一迭代法(用NULL
作为标记)
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> ans;
if (root != NULL) st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
if (node != NULL) {
st.pop();
if (node -> right) st.push(node -> right);
st.push(node);
st.push(NULL);
if (node -> left) st.push(node -> left);
}
else {
st.pop();
node = st.top();
ans.push_back(node -> val);
st.pop();
}
}
return ans;
}
};
原文地址:http://www.cnblogs.com/BarcelonaTong/p/16836797.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性