目录

1.合并二叉树

2. 二叉树的镜像

3.判断是不是二叉搜索树

4. 判断是不是完全二叉树

 5.判断是不是平衡二叉树

1.合并二叉树

找t1/t2是基准树，都在他身上做改动 

  TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {// write code hereif(t1 && t2){t1->val+=t2->val;t1->left=mergeTrees(t1->left, t2->left);t1->right=mergeTrees(t1->right, t2->right);return t1;}else if(t1) return t1;else  return t2;}

2. 二叉树的镜像

注意是一层之间交换，不能写成pRoot->left=Mirror(pRoot->right),这样就找右子树最后一个节点去了 

   TreeNode* Mirror(TreeNode* pRoot) {// write code hereif(!pRoot) return nullptr;TreeNode* p;p=pRoot->left;pRoot->left=pRoot->right;pRoot->right=p;Mirror(pRoot->left);Mirror(pRoot->right);return pRoot;}

3.判断是不是二叉搜索树

    bool _isValidBST(TreeNode* root,TreeNode* min,TreeNode* max){if(!root) return true;if(min && min->val>=root->val) return false;if(max && max->val<=root->val) return false;return _isValidBST(root->left,min,root) && _isValidBST(root->right, root,max);}bool isValidBST(TreeNode* root) {// write code herereturn _isValidBST(root,nullptr,nullptr);}

4. 判断是不是完全二叉树

方法一：借助一个队列，两次入队出队，第一次把所有都入，但是在不为空队的情况下遇到一次空就跳出，来到第二次入队过程，发下 还有空节点那么一定不是完全二叉树 

bool isCompleteTree(TreeNode* root)
{if (root == nullptr)return true;queue q;q.push(root);while (!q.empty()){TreeNode* node = q.front();q.pop();//如果为空，则判断后续队列中有无非空节点，若有非空节点，则返回false。反之返回true。if (node == nullptr) //一直到空跳出{break;}q.push(node->left);//空也压入栈中q.push(node->right);//空也压入栈中}//到这里都是已经遇到空的while (!q.empty()){TreeNode* node = q.front();q.pop();if (node)//还有空直接判错{return false;}}return true;
}

显然这个方法是低效的，两次走队列时间复杂度很高

方法二：

设置一个饱和bool变量，饱和是指一个节点左右孩子都有，只要最少一个孩子不在，就叫不饱和

完全二叉树的不饱和节点只能是最后一个父节点的和一个孩子处

如果饱和变量被设置成false之后还遇到不饱和情况，那么这一不是完全二叉树

 bool isCompleteTree(TreeNode* root) {if(root == nullptr)return true;queue q;q.push(root);bool saturate=true; //饱和while(!q.empty()){TreeNode* p= q.front();q.pop();if(p->left){if(!saturate) return false;q.push(p->left);}else saturate=false; if(p->right){if(!saturate) return false;q.push(p->right);}else saturate=false;    }return true;

 5.判断是不是平衡二叉树

首先这是一个dfs

空树直接是，否则判断左右子树高度差是不是<=1 && 左子树是平衡 && 右子树是平衡

写一个获取高度的函数，空树高度为0, 否则高度为 1+max（左子树高度+右子树高度）

int height(TreeNode* root)
{if(!root) return 0;return 1+max(height(root->left),height(root->right));
}bool IsBalanced_Solution(TreeNode* pRoot) {if(!pRoot) return true;return abs(height(pRoot->left)-height(pRoot->right))<=1 && IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right);}