题目描述： 给定两个二叉树，编写一个函数来检验它们是否相同（两个树在结构上相同，并且节点具有相同的值）。返回bool类型答案。 DFS。给定两个二叉树p和q，采用深度优先搜索，将问题转化为“判断p节点的子树和q节点的子树是否相同”。在遍历到的当前两个节点都为空或者都不为空但值相同的情况下，如果左（右）子树不同，那么p、q对应的子树必然不同，将每层遍历的结果返回到上一层。
class Solution { public: bool isSameTree(TreeNode* p, TreeNode* q) { if(p == NULL && q == NULL) return true; if(p == NULL || q == NULL) return false; if(p -> val != q -> val) return false; if(!isSameTree(p -> left, q -> left)) return false; if(!isSameTree(p -> right, q -> right)) return false; return true; } };题目描述： 给定一个二叉树，检查它是否是镜像对称的。 DFS递归： 将问题转化为比较两个二叉树的左节点和右节点（右节点和左节点）是否相同（两个树在结构上相同，并且节点具有相同的值）的问题。待检查二叉树的根节点同时作为两个拆分后的二叉树的根节点传入函数。每一组对称的节点，其左节点必然等于另一个的右节点，其右节点也必然等于另一个的左节点。
class Solution { public: bool symmetricTree(TreeNode* root1, TreeNode* root2) { if(root1 == NULL && root2 == NULL) return true; if(root1 == NULL || root2 == NULL) return false; if(root1 -> val != root2 -> val) return false; if(!symmetricTree(root1 -> left, root2 -> right)) return false; if(!symmetricTree(root1 -> right, root2 -> left)) return false; return true; } bool isSymmetric(TreeNode* root) { return symmetricTree(root, root); } };迭代： BFS层序遍历将所有节点以及对应的depth存入数组中，遍历该数组，找出相同高度的所有节点，从前后两个方向同时比较节点值，不相同则返回false，同时比较该层节点下一层对应节点的结构是否相同，不同则返回false，相同则继续循环。
bool isSymmetric(TreeNode* root) { if(root == NULL) return true; vector<pair<TreeNode*, int>> vt; queue<pair<TreeNode*, int>> Q; Q.push(make_pair(root, 0)); while(!Q.empty()) { pair<TreeNode*, int> u = Q.front(); Q.pop(); vt.push_back(u); if(u.first->left != NULL) Q.push(make_pair(u.first->left, u.second + 1)); if(u.first->right != NULL) Q.push(make_pair(u.first->right, u.second + 1)); } int r; for(int l=0; l<vt.size(); l=r+1) { r = l; // 找出深度相同的 while(r < vt.size() && vt[r].second == vt[l].second) r++; r--; // 同时前后遍历 for(int i=l, j=r; i<=j; i++, j--) { //比较当前行数相应节点的值 if(vt[i].first->val != vt[j].first->val) return false; //比较下一行数相应节点的结构 bool left1 = (vt[i].first->left == NULL); bool left2 = (vt[j].first->left == NULL); bool right1 = (vt[i].first->right == NULL); bool right2 = (vt[j].first->right == NULL); //cout << vt[i].second << " " << i << " " << j << endl; if(left1 != right2) return false; if(left2 != right1) return false; } } return true; } };题目描述： 翻转一棵二叉树。 DFS。swap( )函数交换每一层对应节点，直到叶子结点。
class Solution { public: void swapTree(TreeNode* root) { if(root -> left != NULL || root -> right != NULL) swap(root -> left, root -> right); if(root -> left != NULL) swapTree(root -> left); if(root -> right != NULL) swapTree(root -> right); return; } TreeNode* invertTree(TreeNode* root) { if(root == NULL) return root; swapTree(root); return root; } };题目描述： 给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。 TreeNode* t3 = new TreeNode(0); DFS, 从上至下，如果两个节点都为空，则直接返回NULL，如果其中一个为空，则返回不为空的节点，保留以该节点为根的子树作为其上一个节点的左子树或右子树。如果两个节点都不为空，则new一个新的节点，其值由对应位置的两个原节点相加获得，其左孩子和右孩子节点由下一层的返回值返回。
class Solution { public: TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) { if(t1 == NULL && t2 == NULL) return t1; if(t1 == NULL || t2 == NULL) { if(t1 == NULL) return t2; if(t2 == NULL) return t1; } else { TreeNode* t3 = new TreeNode(0); t3 -> val = t1 -> val + t2 -> val; t3 -> left = mergeTrees(t1 -> left, t2 -> left); t3 -> right = mergeTrees(t1 -> right, t2 -> right); return t3; } return NULL; } };题目描述： 给定一个二叉树，判断它是否是高度平衡的二叉树。 平衡二叉树（Balanced Binary Tree）具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。 从底至顶对二叉树做深度优先遍历DFS，返回值为一对pair值，为别为高度以及是否是平衡树。在递归过程中，从底至顶，返回以每个节点root为根节点的子树最大高度(左右子树中最大的高度值max(left,right))，当我们发现有一例左/右子树高度差 ＞ 1 的情况时，代表此树不是平衡树，返回false；当发现不是平衡树时，后面的高度计算都没有意义了，因此一路返回false，避免后续多余计算。
class Solution { public: pair<int, bool> compareDep(TreeNode* root, int depth) { if(root -> left == NULL && root -> right == NULL) return make_pair(depth, true); pair<int, bool> left_res = make_pair(depth, true), right_res = make_pair(depth, true); if(root -> left != NULL) { left_res = compareDep(root -> left, depth + 1); if(left_res.second == false) return left_res; } if(root -> right != NULL) { right_res = compareDep(root -> right, depth + 1); if(right_res.second == false) return right_res; } if(abs(left_res.first - right_res.first) > 1) return make_pair(-1, false); return make_pair(max(left_res.first, right_res.first), true); } bool isBalanced(TreeNode* root) { if(root == NULL) return true; return compareDep(root, 0).second; } };改进： 当返回的depth值为-1时，表示以该节点为根节点的子树不是平衡二叉树，当depth值为正数时，表示其对应的子树的最大深度。
class Solution { public: int compareDep(TreeNode* root, int depth) { if(root -> left == NULL && root -> right == NULL) return depth; int left_res = depth, right_res = depth; if(root -> left != NULL) { left_res = compareDep(root -> left, depth + 1); if(left_res == -1) return left_res; } if(root -> right != NULL) { right_res = compareDep(root -> right, depth + 1); if(right_res == -1) return right_res; } if(abs(left_res - right_res) > 1) return -1; return max(left_res, right_res); } bool isBalanced(TreeNode* root) { if(root == NULL) return true; if(compareDep(root, 0) == -1) return false; return true; } };