目录
前言
前天在CSDN上看到了一个著名的学习金字塔图，如下：
这让我想起，我国著名教育学家孔子曾说过：
“学而时习之，不亦说乎？”
所以本着认真负责的态度，打算把这几天学习的二叉树知识消化一下，强化自己对二叉树的理解。
正文
1、二叉平衡搜索树与红黑树的区别
在写第一篇二叉树学习的博客的时，我根据自学二叉树的相关知识，写下了
二叉树学习的一些个人心得。
其实红黑树就是一种二叉平衡搜索树，这两个树不是独立的，
所以C++中
map、multimap、set、multiset的底层实现机制是二叉平衡搜索树
，再具体一点是
红黑树。
2、为什么要给二叉树节点定义构造函数
二叉树的节点函数定义如下：
struct TreeNode {
int val;//值
TreeNode *left;//左子树
TreeNode *right;//右子树
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
定义了如下的构造函数
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
它也可以不写，但是new一个新的节点的时候就比较麻烦。
例如有构造函数，定义初始值为1的节点：
TreeNode* a = new TreeNode(1);
没有构造函数的话就要这么写：
TreeNode* a = new TreeNode();
a->val = 1;
a->left = NULL;
a->right = NULL;
所以，你也能理解为什么需要构造函数了。
3、有没有更牛的二叉树遍历方法
在学习二叉树的遍历的时候，我写下了
递归法
、还有
迭代法
还有一种牛逼的遍历方式：
morris遍历。
morris遍历是二叉树遍历算法的超强进阶算法，morris遍历可以将非递归遍历中的空间复杂度降为O(1)。我其实也没有研究过，以后学习完之后再来补这个坑。
4、递归与迭代哪个方法好
毋庸置疑，从时间复杂度上其实迭代法和递归法差不多（在不考虑函数调用开销和函数调用产生的堆栈开销），但是
空间复杂度上，递归开销会大一些，
因为递归需要系统堆栈存参数返回值等等。
不管怎么说，面试的时候，二叉树的遍历题，
至少递归和迭代都要会写。
5、翻转二叉树的中序遍历递归问题
在写
翻转二叉树学习笔记
时，提到中序遍历不能用递归写法，
否则某些节点的左右孩子会翻转两次。
如果非要使用递归的中序的方式写，也可以，如下：
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == NULL) return root;
invertTree(root->left); // 左
swap(root->left, root->right); // 中
invertTree(root->left); // 注意 这里依然要遍历左孩子，因为中间节点已经翻转了
return root;
}
};
代码虽然可以，但这毕竟不是真正的递归中序遍历了。
但使用迭代方式统一写法的中序是可以的。
如下：
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
stack<TreeNode*> st;
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();
st.pop();
swap(node->left, node->right); // 节点处理逻辑
}
}
return root;
}
};
为什么这个中序就是可以的呢，
因为这是用栈来遍历，而不是靠指针来遍历，避免了递归法中翻转了两次的情况。
每日寄语
总结完后，感觉跟着大佬学习，自己又强大了不少，芜湖~
希望自己有朝一日也能变强。
参考文献