二叉树递归套路解法：
对于需要向左右子节点索取信息的问题，可以使用如下递归套路。
1、对每个节点进行可能性分析，判断是return false 还是return true。
2、递归实现功能。
if 根节点满足某种条件
-
return 递归(左子树) && 递归(右子树)
-
return (递归(左子树) 递归右子树) （其中一个满足条件即可）
return false
二叉树的四种遍历方式
二叉树的前序（中左右）、中序（左中右）、后序遍历（左右中）、层次遍历是基础的概念，这里以一个简单二叉树为例进行分析。如下图：
-
前序遍历：1、2、4、5、3、6、7
-
中序遍历：4、2、5、1、6、3、7
-
后序遍历：4、5、2、6、7、3、1
-
层次遍历：1、2、3、4、5、6、7
根据前序遍历和中序遍历还原树的形状
- 前序遍历第一个是头结点（本例为1），根据头结点在中序遍历的位置（即1）可以把树划分为左右子树（4、2、5和6、3、7）。
- 根据中序遍历划分的子树可以把前序遍历也被划分为左右子树（2、4、5和3、6、7），然后根据前序遍历划分的子树可以找到两个子树的头结点（2和3）。
- 以此类推可以还原出树的形状。
递归序指的是采用递归遍历二叉树的方式实现，其过程为
1、2、4、4、4、2、5、5、5、2
1、3、6、6、6、3、7、7、7、3、1
其中4等数字出现三次的原因是：1）先按照1、2、4的顺序到达4结点。 2）4先找左孩子为空，返回4。 3）4再找右孩子为空，返回4。
-
第一次到达结点的时候打印是：前序遍历
-
第一次到达结点的时候打印是：中序遍历
-
第一次到达结点的时候打印是：后序遍历
以下是递归序遍历输出前序遍历、中序遍历、中序遍历的代码
class Solution {
public:
vector<int> Traversal(TreeNode* root) {
vector<int> res;
if (root== NULL) return vector<int>();
preOrderRecur(root, res);
//inOrderRecur(root, res);
//posOrderRecur(root, res);
return res;
}
void preOrderRecur(TreeNode* root, vector<int> &res){
if (root){
res.push_back(root->val); //前序遍历
preOrderRecur(root->left, res);
preOrderRecur(root->right, res);
}
}
void inOrderRecur(TreeNode* root, vector<int> &res){
if (root){
inOrderRecur(root->left, res);
res.push_back(root->val); //中序遍历
inOrderRecur(root->right, res);
}
}
void posOrderRecur(TreeNode* root, vector<int> &res){
if (root){
posOrderRecur(root->left, res);
posOrderRecur(root->right, res);
res.push_back(root->val); //后序遍历
}
}
};
上述为递归实现的过程，任何算法的递归版本都可以改成非递归版本，因为函数递归调用其实质就是压栈的过程，那么我们完全可以使用堆栈来模拟这个过程，并且面试过程可能会考察三种遍历方式的迭代形式
前序遍历(leetcode-144)
前序遍历主要借助栈来实现，是中左右的过程，首先压入根结点，此时栈不为空，进入循环。然后弹出当前结点，弹出的时候打印结点。如果右孩子存在，右孩子压入栈内。如果左孩子存在，左孩子压入栈内。先右后左依次压栈，弹出的时候就会是先左后右打印，对于每个结点循环这个过程就实现的前序遍历。
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
if (!root) return vector <int> ();
stack <TreeNode*> s;
TreeNode* p = root;
vector<int> res;
while (!s.empty() || p){
while (p){
s.push(p);
res.push_back(p->val);
p = p->left;
}
p = s.top();
s.pop();
p = p->right;
}
return res;
}
};
中序遍历 leetcode-94
中序时，我们首先去遍历整个二叉树的左分支，并依次将节点压入栈中，直到找到最左边的叶节点，然后弹出并打印，并看其有没右分支；如果没有，返回上一级并弹出当前根节点，然后看其有没有右分支。每次弹出，都要观察其是否有右分支，也就是说每个节点都遍历了两次！（整个过程先处理整个树的左边界，然后处理右树的左边界）
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
if (root == NULL) return vector<int>();
stack <TreeNode*>s;
vector<int> res;
TreeNode* p = root;
while (!s.empty() || p){
if (p) {
s.push (p);
p = p->left;
}
else {
p = s.top();
s.pop();
res.push_back(p->val);
p = p->right;
}
}
return res;
}
};
后序遍历 leetcode-145
后序遍历是在前序遍历的基础上做的，前序遍历的压栈顺序为：根、左、右，后续遍历为左、右、根。一个简单的思想是使用两个栈，一个压入的顺序是先左后右，从第一个栈弹出再压入第二个栈的时候就是先右后左了，并且此时根节点最先压入，打印的时候就会是左、右、根了。
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
if (root == NULL) return vector<int>();
vector<int> res;
stack <TreeNode*> s1;
stack <TreeNode*> s2;
TreeNode* p = root;
s1.push(p);
while (!s1.empty()){
p = s1.top();
s1.pop();
s2.push(p);
if (p->left) s1.push(p->left);
if (p->right) s1.push(p->right);
}
while (!s2.empty()){
p = s2.top();
s2.pop();
res.push_back(p->val);
}
return res;
}
};
二叉树树相关概念及判断实现
判断是否为完全二叉树
完全二叉树：所有的叶节点全部在底层，并且在底层全部铺满的二叉树
完全二叉树的判断一般采用宽度优先遍历，即层次遍历，可以使用队列来实现。
两个判断false的条件：
-
如果当前节点的右孩子节点不为空，而左孩子节点为空，直接判断false。
-
如果当前节点的左右孩子节点如果有一个为空，我们标记leaf=True，也就是往后遍历的节点的孩子节点必须都为空，否则返回false。
public static boolean isCBT(Node head) {
if (head == null) {
return true;
}
LinkedList<Node> queue = new LinkedList<>();
boolean leaf = false;
Node l = null;
Node r = null;
queue.add(head);
while (!queue.isEmpty()) {
head = queue.poll();
l = head.left;
r = head.right;
if ((leaf && (l != null || r != null)) || (l == null && r != null)) {
return false;
}
if (l != null) {
queue.add(l);
}
if (r != null) {
queue.add(r);
} else {
leaf = true;
}
}
return true;
}
判断是否为搜索二叉树 leetcode-98
二叉搜索树：二叉搜索树不允许重复的数值存在，要求每个节点本身大于其左子树，而小于其右子树，对其进行中序遍历后，会得到一个有序的列表。
二叉搜索树中序遍历后为一个有序数组，即左<中<右，因此可以在中序遍历代码的基础上进行改进，我们使用中序遍历可以得到每一个节点，然后当前节点的值和前一个节点的值进行比较，如果大于，那么继续遍历，否则我们返回false！如果可以成功遍历每个节点，并都满足那个比较条件，那么返回true。
class Solution {
public:
bool isValidBST(TreeNode* root) {
if (root == NULL) return true;
stack <TreeNode*> s;
TreeNode* p = root;
double pre = - DBL_MAX;
while (!s.empty() || p){
if (p){
s.push(p);
p = p->left;
}
else{
p = s.top();
s.pop();
if (p->val <= pre) return false;
pre = p->val;
p = p->right;
}
}
return true;
}
};
}
判断是否是二叉平衡树 leetcode-110
平衡二叉树：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，并且满足二叉搜索树的规则。
这里面就存在一个套路，因为判断是否为平衡二叉树的规则对于每个节点都是一致的，也就是说当前节点左子树的高度和其右子树的高度高度差不能超过1，这就很显然可以使用一个递归函数来对每个节点进行遍历，并判断！对于这个递归函数而言，其输入参数应该为当前树的根节点（子树头结点），而返回值为当前树的高度(int)以及是否为平衡树(bool)。对于整棵树而言，只要任意一个子树不为平衡二叉树，那么整个数也不会为平衡二叉树。
另一个递归函数是求树的最大深度 leetcode-104，递归的套路是一致的。
class Solution {
public:
bool isBalanced(TreeNode* root) {
if(!root) return true;
if (abs(maxdepth(root->left)-maxdepth(root->right)) < 2){
return isBalanced(root->left) && isBalanced(root->right);
}
return false;
}
int maxdepth(TreeNode* root){
if(root == NULL) return 0;
return max(maxdepth(root->left)+1, maxdepth(root->right)+1);
}
};
