力扣236. 二叉树的最近公共祖先:【递归与回溯】详解 解题思路：
完整版：
class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (root == q || root == p || root == NULL) return root; TreeNode* left = lowestCommonAncestor(root->left, p, q); TreeNode* right = lowestCommonAncestor(root->right, p, q); if (left != NULL && right != NULL) return root; if (left == NULL && right != NULL) return right; else if (left != NULL && right == NULL) return left; else { // (left == NULL && right == NULL) return NULL; } } }; 作者：carlsun-2 链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/236-er-cha-shu-de-zui-jin-gong-gong-zu-xian-di-g-2/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。精减版：
class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (root == q || root == p || root == NULL) return root; TreeNode* left = lowestCommonAncestor(root->left, p, q); TreeNode* right = lowestCommonAncestor(root->right, p, q); if (left != NULL && right != NULL) return root; if (left == NULL) return right; return left; } }; 作者：carlsun-2 链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/236-er-cha-shu-de-zui-jin-gong-gong-zu-xian-di-g-2/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。力扣235. 二叉搜索树的最近公共祖先:【递归】详解 解题思路： 完整版：
class Solution { private: TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q) { if (cur == NULL) return cur; // 中 if (cur->val > p->val && cur->val > q->val) { // 左 TreeNode* left = traversal(cur->left, p, q); if (left != NULL) { return left; } } if (cur->val < p->val && cur->val < q->val) { // 右 TreeNode* right = traversal(cur->right, p, q); if (right != NULL) { return right; } } return cur; } public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { return traversal(root, p, q); } }; 作者：carlsun-2 链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/solution/235-er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu--24/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。精减版：
class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (root->val > p->val && root->val > q->val) { return lowestCommonAncestor(root->left, p, q); } else if (root->val < p->val && root->val < q->val) { return lowestCommonAncestor(root->right, p, q); } else return root; } }; 作者：carlsun-2 链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/solution/235-er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu--24/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。力扣104.二叉树的最大深度 完整版：
class Solution { public: int getDepth(TreeNode* node) { if (node == NULL) return 0; int leftDepth = getDepth(node->left); // 左 int rightDepth = getDepth(node->right); // 右 int depth = 1 + max(leftDepth, rightDepth); // 中 return depth; } int maxDepth(TreeNode* root) { return getDepth(root); } }; 作者：carlsun-2 链接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/solution/qiu-shu-de-zui-da-shen-du-xiang-jie-by-carlsun-2/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。精减版：
class Solution { public: int maxDepth(TreeNode* root) { if (root == NULL) return 0; return 1 + max(maxDepth(root->left), maxDepth(root->right)); } }; 作者：carlsun-2 链接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/solution/qiu-shu-de-zui-da-shen-du-xiang-jie-by-carlsun-2/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。力扣617. 合并二叉树:【递归】
class Solution { public: TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) { if (t1 == NULL) return t2; // 如果t1为空，合并之后就应该是t2 if (t2 == NULL) return t1; // 如果t2为空，合并之后就应该是t1 // 修改了t1的数值和结构 t1->val += t2->val; // 中 t1->left = mergeTrees(t1->left, t2->left); // 左 t1->right = mergeTrees(t1->right, t2->right); // 右 return t1; } }; 作者：carlsun-2 链接：https://leetcode-cn.com/problems/merge-two-binary-trees/solution/617-he-bing-er-cha-shu-san-chong-di-gui-yi-chong-d/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。力扣110. 平衡二叉树:【递归】
class Solution { public: // 返回以该节点为根节点的二叉树的高度，如果不是二叉搜索树了则返回-1 int getDepth(TreeNode* node) { if (node == NULL) { return 0; } int leftDepth = getDepth(node->left); if (leftDepth == -1) return -1; // 说明左子树已经不是二叉平衡树 int rightDepth = getDepth(node->right); if (rightDepth == -1) return -1; // 说明右子树已经不是二叉平衡树 return abs(leftDepth - rightDepth) > 1 ? -1 : 1 + max(leftDepth, rightDepth); } bool isBalanced(TreeNode* root) { return getDepth(root) == -1 ? false : true; } }; 作者：carlsun-2 链接：https://leetcode-cn.com/problems/balanced-binary-tree/solution/110-ping-heng-er-cha-shu-di-gui-san-bu-qu-xiang-ji/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。力扣112. 路径总和 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。 遍历的路线，并不要遍历整棵树，所以递归函数需要返回值，可以用bool类型表示。 完整思路版：
class Solution { private: bool traversal(TreeNode* cur, int count) { if (!cur->left && !cur->right && count == 0) return true; // 遇到叶子节点，并且计数为0 if (!cur->left && !cur->right) return false; // 遇到叶子节点直接返回 if (cur->left) { // 左 count -= cur->left->val; // 递归，处理节点; if (traversal(cur->left, count)) return true; count += cur->left->val; // 回溯，撤销处理结果 } if (cur->right) { // 右 count -= cur->right->val; // 递归，处理节点; if (traversal(cur->right, count)) return true; count += cur->right->val; // 回溯，撤销处理结果 } return false; } public: bool hasPathSum(TreeNode* root, int sum) { if (root == NULL) return false; return traversal(root, sum - root->val); } };精减版：
class Solution { public: bool hasPathSum(TreeNode* root, int sum) { if (root == NULL) return false; if (!root->left && !root->right && sum == root->val) { return true; } return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val); } };力扣113. 路径总和II 给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。 思路：路径总和II要遍历整个树，找到所有路径，所以递归函数不要返回值。
class Solution { private: vector<vector<int>> result; vector<int> path; // 递归函数不需要返回值，因为我们要遍历整个树 void traversal(TreeNode* cur, int count) { if (!cur->left && !cur->right && count == 0) { // 遇到了叶子节点切找到了和为sum的路径 result.push_back(path); return; } if (!cur->left && !cur->right) return ; // 遇到叶子节点而没有找到合适的边，直接返回 if (cur->left) { // 左 （空节点不遍历） path.push_back(cur->left->val); count -= cur->left->val; traversal(cur->left, count); // 递归 count += cur->left->val; // 回溯 path.pop_back(); // 回溯 } if (cur->right) { // 右 （空节点不遍历） path.push_back(cur->right->val); count -= cur->right->val; traversal(cur->right, count); // 递归 count += cur->right->val; // 回溯 path.pop_back(); // 回溯 } return ; } public: vector<vector<int>> pathSum(TreeNode* root, int sum) { result.clear(); path.clear(); if (root == NULL) return result; path.push_back(root->val); // 把根节点放进路径 traversal(root, sum - root->val); return result; } }; 作者：carlsun-2 链接：https://leetcode-cn.com/problems/path-sum/solution/112-lu-jing-zong-he-di-gui-hui-su-die-dai-xiang-ji/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。力扣572. 另一个树的子树 给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。 思路： 1.从上向下遍历 s 树的各个叶子节点 2.如果 s 的叶子节点值跟 t 树根节点值一样，即可进入判断同一棵树程序 3.使用 dfs 判断是否是同一棵树
class Solution { public: bool isSubtree(TreeNode* s, TreeNode* t) { if (s == nullptr) return false; if (dfs(s, t)) return true; return (isSubtree(s->left, t) || isSubtree(s->right, t)); } bool dfs(TreeNode* s, TreeNode* t) { if (s == nullptr && t == nullptr) return true; if (s == nullptr || t == nullptr) return false; if (s->val != t->val) return false; return (dfs(s->left, t->left) && dfs(s->right, t->right)); } }; 作者：ikaruga 链接：https://leetcode-cn.com/problems/subtree-of-another-tree/solution/subtree-of-another-tree-by-ikaruga/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。力扣剑指 Offer 26. 树的子结构 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构) B是A的子结构， 即 A中有出现和B相同的结构和节点值。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool isSubStructure(TreeNode* A, TreeNode* B) { if(!A || !B) return false; bool res = false; // 如果在 A 中匹配到了与 B 的根节点的值一样的节点 if(A -> val == B -> val) res = doesAHaveB(A, B); // 如果匹配不到，A 往左 if(!res) res = isSubStructure(A -> left, B); // 还匹配不到，A 往右 if(!res) res = isSubStructure(A -> right, B); return res; } bool doesAHaveB(TreeNode *r1, TreeNode *r2) { // 如果 B 已经遍历完了，true if(!r2) return true; // 如果 B 还有，但 A 遍历完了，那 B 剩下的就没法匹配了，false if(!r1) return false; // 不相等，false if(r1 -> val != r2 -> val) return false; return doesAHaveB(r1 -> left, r2 -> left) && doesAHaveB(r1 -> right, r2 -> right); } }; 作者：superkakayong 链接：https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/solution/zi-jie-ti-ku-jian-26-zhong-deng-shu-de-zi-jie-gou-/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。力扣543. 二叉树的直径 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
思路：首先我们知道一条路径的长度为该路径经过的节点数减一，所以求直径（即求路径长度的最大值）等效于求路径经过节点数的最大值减一。 而任意一条路径均可以被看作由某个节点为起点，从其左儿子和右儿子向下遍历的路径拼接得到。
class Solution { int ans; int depth(TreeNode* rt){ if (rt == NULL) { return 0; // 访问到空节点了，返回0 } int L = depth(rt->left); // 左儿子为根的子树的深度 int R = depth(rt->right); // 右儿子为根的子树的深度 ans = max(ans, L + R + 1); // 计算d_node即L+R+1 并更新ans return max(L, R) + 1; // 返回该节点为根的子树的深度 } public: int diameterOfBinaryTree(TreeNode* root) { ans = 1; depth(root); return ans - 1; } }; 作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/diameter-of-binary-tree/solution/er-cha-shu-de-zhi-jing-by-leetcode-solution/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。力扣114. 二叉树展开为链表 给定一个二叉树，原地将它展开为一个单链表。
例如，给定二叉树 1 / \ 2 5 / \ \ 3 4 6 将其展开为： 1 \ 2 \ 3 \ 4 \ 5 \ 6 class Solution { public: //采用前序遍历，根左右 void flatten(TreeNode* root) { //前序遍历 if(!root) return; //保留右子树 TreeNode* oldrigt = root->right; //把左子树放到原来右子树的位置 root->right = root->left; //左子树接到NULL上 root->left = NULL; //找到原先左子树的最右节点 TreeNode* rightNode = root; while(rightNode->right != NULL){ rightNode = rightNode->right; } //将原先的左子树接到rightNode的右子树上 rightNode->right = oldrigt; //按照前序遍历的次序，递归调用左子树，但是左子树已经指向NULL，因此可省去 //flatten(root->left); flatten(root->right); } };