给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1 / \ 2 2 / \ / \ 3 4 4 3但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1 / \ 2 2 \ \ 3 3说明: 如果你可以运用递归和迭代两种方法解决这个问题，会很加分。
/** * 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 isSymmetric(TreeNode* root) { //递归 return !root || dfs(root->left, root->right); } bool dfs(TreeNode *p, TreeNode *q) { if(!p || !q) return !p && !q;//两个都空 对称 return p->val == q->val && dfs(p->left, q->right) && dfs(p->right, q->left); } }; class Solution { public: bool isSymmetric(TreeNode* root) { //迭代 if(!root) return true; stack<TreeNode*> left, right; TreeNode *lc = root->left; TreeNode *rc = root->right; while(lc || rc || left.size())//对根节点的左子树，我们用中序遍历 { while(lc && rc) { left.push(lc), right.push(rc); lc = lc->left, rc = rc->right; } if(lc || rc) return false; lc = left.top(), rc = right.top(); left.pop(), right.pop(); if(lc->val != rc->val) return false; lc = lc->right, rc = rc->left; //对根节点的右子树，我们用反中序遍历 } return true; } };给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例： 给定二叉树 [3,9,20,null,null,15,7]，
3 / \ 9 20 / \ 15 7返回它的最大深度 3 。
/** * 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: int maxDepth(TreeNode* root) { return root ? max(maxDepth(root->left), maxDepth(root->right)) + 1 : 0; } };给定一个二叉树，返回它的 后序 遍历。
示例:
输入: [1,null,2,3]
1 \ 2 / 3输出: [3,2,1]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
/** * 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: vector<int> res; vector<int> postorderTraversal(TreeNode* root) { //递归 if(!root) return res; postorderTraversal(root->left); postorderTraversal(root->right); res.push_back(root->val); return res; } };据一棵树的前序遍历与中序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3 / \ 9 20 / \ 15 7 /** * 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: unordered_map<int, int>pos; TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { int n = preorder.size(); for(int i = 0; i < n; i ++) pos[inorder[i]] = i;//记录所有权值在中序遍历的位置 return dfs(preorder, inorder, 0, n - 1, 0, n - 1); } /* pl = preorder-left, pr = preorder-right, il = inorder-left, ir = inorder-right pl, pr分别表示当前子树的前序遍历在整个preorder遍历数组中的起止坐标 il,ir分别表示当前子树的中序遍历在整个inorder数组中的起止下标 这里的left和right不表示左右子树，表示的是数组中区间的左右端点 */ TreeNode* dfs(vector<int>&pre, vector<int>&in, int pl, int pr, int il, int ir) { if(pl > pr) return NULL; int k = pos[pre[pl]] - il; //前序遍历第一个元素 减去 中序遍历的左长度 就是根节点在中序的位置 TreeNode *root = new TreeNode(pre[pl]);//建立根节点 root->left = dfs(pre, in, pl + 1, pl + k, il, il + k - 1); root->right = dfs(pre, in, pl + 1 + k, pr, il + 1 + k, ir);//1是根 return root; } };序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。
_9_ / \ 3 2 / \ / \ 4 1 # 6 / \ / \ / \ # # # # # #例如，上面的二叉树可以被序列化为字符串 “9,3,4,#,#,1,#,#,2,#,6,#,#”，其中 # 代表一个空节点。
给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。
每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 ‘#’ 。
你可以认为输入格式总是有效的，例如它永远不会包含两个连续的逗号，比如 “1,3” 。
示例 1:
输入: “9,3,4,#,#,1,#,#,2,#,6,#,#” 输出: true
示例 2:
输入: “1,#” 输出: false
示例 3:
输入: “9,#,#,1” 输出: false
class Solution { public: bool ans = true; bool isValidSerialization(string preorder) { preorder += ',';//在最后加一个, int u = 0; dfs(preorder, u); //如果递归还没结束但数组已经遍历完， //或者递归结束但数组还没遍历完，则说明给定的序列不是一个合法的前序遍历。 return ans && u == preorder.size(); } void dfs(string &preorder, int &u) { //没有遍历完 但是序列已经结束 不合法 if(u == preorder.size()) { ans = false; return; } if(preorder[u] == '#') { u += 2; return; } while(preorder[u] != ',') u ++; u ++; //把逗号略过 dfs(preorder, u);//遍历左子树 if(u == preorder.size()) { ans = false; return; } dfs(preorder, u);//遍历右子树 } };给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。
例如: 给定二叉树: [3,9,20,null,null,15,7],
3 / \ 9 20 / \ 15 7返回其层次遍历结果：
[ [3], [9,20], [15,7] ]
/** * 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: vector<int> get_val(vector<TreeNode*> level) { vector<int>res; for(auto &u : level) res.push_back(u->val); return res; } vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> res; if(!root) return res; vector<TreeNode*>level;//每层 level.push_back(root); res.push_back(get_val(level)); while(true) { vector<TreeNode*> newlevel;//开新队列 for(auto &u : level) { if(u->left) newlevel.push_back(u->left); if(u->right) newlevel.push_back(u->right); } if(newlevel.size()) { res.push_back(get_val(newlevel)); level = newlevel;//新层 赋值到 当前层 } else break; } return res; } };给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。
案例 1:
输入:
5 / \ 3 6 / \ \ 2 4 7Target = 9
输出: True
案例 2:
输入:
5 / \ 3 6 / \ \ 2 4 7Target = 28
输出: False
/** * 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: vector<int> inorder; bool findTarget(TreeNode* root, int k) { dfs(root); for(int i = 0, j = inorder.size() - 1; i < j; i ++)//两个指针前后扫描 { while(i < j && inorder[i] + inorder[j] > k) j--;//太大 第二指针往左移 if(i < j && inorder[i] + inorder[j] == k) return true; } return false; } void dfs(TreeNode *root) { if(!root) return; dfs(root->left); inorder.push_back(root->val); dfs(root->right); } };给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出: 3 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出: 5 解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
说明: 所有节点的值都是唯一的。 p、q 为不同节点且均存在于给定的二叉树中。
/** * 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: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(!root || root == p || root == q) return root; TreeNode* left = lowestCommonAncestor(root->left, p, q); TreeNode* right = lowestCommonAncestor(root->right, p, q); if(left && right) return root; else if(!left && right) return right; else if(left && !right) return left; else return NULL; } };给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
示例 : 给定二叉树
1 / \ 2 3 / \ 4 5返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
/** * 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: int ans = 0; int diameterOfBinaryTree(TreeNode* root) { dfs(root); return ans; } int dfs(TreeNode *u) { if(!u) return 0; int l = dfs(u->left); int r = dfs(u->right); // cout << l << " " << r << endl; ans = max(ans, l + r); //更新答案 return max(l, r) + 1; } };给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
示例 1:
输入: [1,2,3]
1 / \ 2 3输出: 6
示例 2:
输入: [-10,9,20,null,null,15,7]
-10 / \ 9 20 / \ 15 7输出: 42
/** * 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: int ans; int maxPathSum(TreeNode* root) { ans = INT_MIN; dfs(root); return ans; } int dfs(TreeNode* u) { if(!u) return 0; int l = max(0, dfs(u->left)); int r = max(0, dfs(u->right)); ans = max(ans, l + r + u->val); return u->val + max(l, r); } };给定一个字符串 s1，我们可以把它递归地分割成两个非空子字符串，从而将其表示为二叉树。
下图是字符串 s1 = “great” 的一种可能的表示形式。
great / \ gr eat / \ / \ g r e at / \ a t在扰乱这个字符串的过程中，我们可以挑选任何一个非叶节点，然后交换它的两个子节点。 例如，如果我们挑选非叶节点 “gr” ，交换它的两个子节点，将会产生扰乱字符串 “rgeat” 。
rgeat / \ rg eat / \ / \ r g e at / \ a t我们将 "rgeat” 称作 “great” 的一个扰乱字符串。 同样地，如果我们继续将其节点 “eat” 和 “at” 进行交换，将会产生另一个新的扰乱字符串 “rgtae” 。
rgtae / \ rg tae / \ / \ r g ta e / \ t a我们将 "rgtae” 称作 “great” 的一个扰乱字符串。
给出两个长度相等的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。
示例 1:
输入: s1 = “great”, s2 = “rgeat” 输出: true
示例 2:
输入: s1 = “abcde”, s2 = “caebd” 输出: false
class Solution { public: bool isScramble(string s1, string s2) { if(s1 == s2) return true; string ss1 = s1, ss2 = s2; sort(ss1.begin(),ss1.end()), sort(ss2.begin(), ss2.end()); if(ss1 != ss2) return false; //该节点不发生翻转，则分别判断两个字符串的左右两部分是否分别可以相互转化； //该节点发生翻转，则分别判断第一个字符串的左边是否可以和第二个字符串的右边相互转化， //且第一个字符串的右边可以和第二个字符串的左边相互转化； for(int i = 1; i < s1.size(); i++) { if(isScramble(s1.substr(0, i), s2.substr(0, i)) && isScramble(s1.substr(i), s2.substr(i))) return true; if(isScramble(s1.substr(0, i), s2.substr(s2.size() - i)) && isScramble(s1.substr(i), s2.substr(0, s2.size() - i))) return true; } return false; } };给定一个二叉树
struct Node { int val; Node *left; Node *right; Node *next; }
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
示例：
输入：{“KaTeX parse error: Expected '}', got 'EOF' at end of input: …":"1","left":{"id”:“2”,“left”:{“KaTeX parse error: Expected 'EOF', got '}' at position 53: …t":null,"val":4}̲,"next":null,"r…id”:“4”,“left”:null,“next”:null,“right”:null,“val”:5},“val”:2},“next”:null,“right”:{“KaTeX parse error: Expected '}', got 'EOF' at end of input: …null,"right":{"id”:“6”,“left”:null,“next”:null,“right”:null,“val”:7},“val”:3},“val”:1}
输出：{“KaTeX parse error: Expected '}', got 'EOF' at end of input: …":"1","left":{"id”:“2”,“left”:{“KaTeX parse error: Expected '}', got 'EOF' at end of input: …:null,"next":{"id”:“4”,“left”:null,“next”:{“KaTeX parse error: Expected 'EOF', got '}' at position 53: …t":null,"val":7}̲,"right":null,"…id”:“6”,“left”:null,“next”:null,“right”:{“KaTeX parse error: Expected 'EOF', got '}' at position 9: ref":"5"}̲,"val":3},"righ…ref”:“4”},“val”:2},“next”:null,“right”:{"$ref":“6”},“val”:1}
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。
提示： 你只能使用常量级额外空间。 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
/* // Definition for a Node. class Node { public: int val; Node* left; Node* right; Node* next; Node() {} Node(int _val, Node* _left, Node* _right, Node* _next) { val = _val; left = _left; right = _right; next = _next; } }; */ class Solution { public: Node* connect(Node* _root) { Node* root = _root; while(root) { Node *dummy = new Node(0); Node *tail = dummy; while(root) { if(root->left) { tail->next = root->left; tail = tail->next; } if(root->right) { tail->next = root->right; tail = tail->next; } root = root->next; } tail->next = 0; root = dummy->next; } return _root; } };在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
示例 1:
输入: [3,2,3,null,3,null,1]
3 / \ 2 3 \ \ 3 1输出: 7 解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
示例 2:
输入: [3,4,5,1,3,null,1]
3 / \ 4 5 / \ \ 1 3 1输出: 9 解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ /* (树形动规) O(n) 典型的树形DP问题。 状态表示： f[i][0]表示已经偷完以 i为根的子树，且不在 i行窃的最大收益； f[i][1]表示已经偷完以 i为根的子树，且在 i 行窃的最大收益； 状态转移： f[i][1]：因为在 i行窃，所以在 i的子节点不能行窃，只能从f[i->left][0]和f[i->right][0]转移； f[i][0]：因为不在 i行窃，所以对 i 的子节点没有限制，直接用左右子节点的最大收益转移即可； */ class Solution { public: unordered_map<TreeNode*, unordered_map<int, int>>f; int rob(TreeNode* root) { dfs(root); return max(f[root][0], f[root][1]); } void dfs(TreeNode *root) { if(!root) return; dfs(root->left); dfs(root->right); f[root][1] = root->val + f[root->left][0] + f[root->right][0]; f[root][0] = max(f[root->left][0], f[root->left][1]) + max(f[root->right][0], f[root->right][1]); } };二叉搜索树中的两个节点被错误地交换。
请在不改变其结构的情况下，恢复这棵树。
示例 1:
输入: [1,3,null,null,2]
1 / 3 \ 2输出: [3,1,null,null,2]
3 / 1 \ 2示例 2:
输入: [3,1,4,null,null,2]
3 / \ 1 4 / 2输出: [2,1,4,null,null,3]
2 / \ 1 4 / 3进阶: 使用 O(n) 空间复杂度的解法很容易实现。 你能想出一个只使用常数空间的解决方案吗？
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ /* 从根节点开始遍历，直至当前节点为空为止： 如果当前节点没有左儿子，则打印当前节点的值，然后进入右子树； 如果当前节点有左儿子，则找当前节点的前驱。 (1) 如果前驱节点的右儿子为空，说明左子树没遍历过，则进入左子树遍历，并将前驱节点的右儿子置成当前节点，方便回溯； (2) 如果前驱节点的右儿子为当前节点，说明左子树已被遍历过，则将前驱节点的右儿子恢复为空，然后打印当前节点的值，然后进入右子树继续遍历； */ class Solution { public: void recoverTree(TreeNode* root) { TreeNode *first = NULL, *second, *prep = NULL; while(root) { if(!root->left) { if(prep && prep->val > root->val) { if(!first) first = prep, second = root; else second = root; } prep = root; root = root->right; } else { TreeNode *p = root->left; while(p->right && p->right != root) p = p->right; if(!p->right) { p->right = root; root = root->left; } else { p->right = NULL; if(prep && prep->val > root->val) { if(!first) first = prep, second = root; else second = root; } prep = root; root = root->right; } } } swap(first->val, second->val); } };