94. 二叉樹的中序遍歷
class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> ans;stack<TreeNode*> stk;while (root || stk.size()) {while (root) {stk.push(root);root = root->left;}auto cur = stk.top();stk.pop();ans.push_back(cur->val);root = cur->right;}return ans;}
};class Solution {
public:int maxDepth(TreeNode* root) {auto dfs = [&](this auto&& dfs, TreeNode* root) -> int {if (root == NULL) return 0;return max(dfs(root->left), dfs(root->right)) + 1;};return dfs(root);}
};使用棧模擬
中序遍歷本質是根在中，從左往右
因此一開始就先往左邊找，找不到的情況下，說明可以往右邊找了，然后又變成了一個子問題
104. 二叉樹的最大深度
class Solution {
public:int maxDepth(TreeNode* root) {auto dfs = [&](this auto&& dfs, TreeNode* root) -> int {if (root == NULL) return 0;return max(dfs(root->left), dfs(root->right)) + 1;};return dfs(root);}
};?經典模擬題
226. 翻轉二叉樹
class Solution {
public:TreeNode* invertTree(TreeNode* root) {auto dfs = [](this auto&& dfs, TreeNode* root) -> void {if (root == NULL) return;TreeNode* tmp = root->left;root->left = root->right;root->right = tmp;dfs(root->left);dfs(root->right);};dfs(root);return root;}
};交換指針的時候注意tmp保存
101. 對稱二叉樹
class Solution {
public:bool isSymmetric(TreeNode* root) {auto dfs = [](this auto&& dfs, TreeNode* p1, TreeNode* p2) -> bool {if ((p1 && !p2) || (!p1 && p2) || (p1 && p2 && p1->val != p2->val)) return false;if (!p1 && !p2) return true;return dfs(p1->left, p2->right) && dfs(p1->right, p2->left);};return dfs(root->left, root->right);}
};?模擬：分情況考慮即可
543. 二叉樹的直徑
class Solution {
public:int diameterOfBinaryTree(TreeNode* root) {int ans = 0;auto dfs = [&](this auto&& dfs, TreeNode* root) -> int {if (root->left && root->right) {int t1 = max(dfs(root->left), 0);int t2 = max(dfs(root->right), 0);int t = t1 + t2 + 1;ans = max(ans, t);return max(t1, t2) + 1;}else if (root->left) {int t = max(dfs(root->left), 0) + 1;ans = max(ans, t);return t;}else if (root->right) {int t = max(dfs(root->right), 0) + 1;ans = max(ans, t);return t;}else {ans = max(ans, 1);return 1;}};dfs(root);return ans - 1;}
};?維護以root為根節點（包含在內）的單鏈最長?
?102. 二叉樹的層序遍歷
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> v(2000);if (root == NULL) return {};queue<pair<TreeNode*, int>> q;q.push({root, 0});while (q.size()) {pair<TreeNode*, int> now = q.front();q.pop();auto u = now.first;int dep = now.second;v[dep].push_back(u->val);if (u->left) {q.push({ u->left , dep + 1});}if (u->right) {q.push({ u->right , dep + 1});}}vector<vector<int>> ans;for (auto vec : v) {if (vec.size()) ans.push_back(vec);}return ans;}
};?BFS記錄深度
?108. 將有序數組轉換為二叉搜索樹
class Solution {
public:TreeNode* sortedArrayToBST(vector<int>& nums) {auto dfs = [&](this auto&& dfs,int l, int r) -> TreeNode* {if (l > r) return NULL;int mid = (l + r) / 2;TreeNode* root = new TreeNode(nums[mid]);root->left = dfs(l, mid - 1);root->right = dfs(mid + 1, r);return root;};return dfs(0, nums.size() - 1);}
};利用中序遍歷的有序性，每次選擇中間節點作為根節點，劃分子問題
98. 驗證二叉搜索樹
class Solution {
public:bool isValidBST(TreeNode* root) {auto dfs = [](this auto&& dfs, TreeNode* root, long long l, long long r) -> bool {if (root == NULL) return true;if (root->val <= l || root->val >= r) return false;return dfs(root->left, l, root->val) && dfs(root->right, root->val, r);};return dfs(root, LONG_MIN, LONG_MAX);}
};函數表示考慮以?
root?為根的子樹，判斷子樹中所有節點的值是否都在?(l,r)?的范圍內（注意是開區間）。同時注意開long long
230. 二叉搜索樹中第 K 小的元素
class Solution {
public:int kthSmallest(TreeNode* root, int k) {// vector<int> v;int ans;auto dfs = [&](this auto&& dfs, TreeNode* root) -> bool {if (root == NULL) return false;if (dfs(root->left)) return true;k--;if (k == 0) {ans = root->val;return true;}return dfs(root->right);};dfs(root);return ans;}
};利用平衡二叉樹的中序遍歷的有序性
199. 二叉樹的右視圖
class Solution {
public:vector<int> rightSideView(TreeNode* root) {if (root == NULL) return {};vector<int> ans;queue<TreeNode*> q;q.push(root);while (q.size()) {vector<TreeNode*> v;while (q.size()) {v.push_back(q.front());q.pop();}ans.push_back(q.back()->val);for (auto root : v) {if (root->left)q.push(root->left);if (root->right)q.push(root->right);}}return ans;}
};?層序遍歷每一層的最右邊節點就是答案
114. 二叉樹展開為鏈表
class Solution {
public:void flatten(TreeNode* root) {TreeNode* dummy = new TreeNode(0);TreeNode* cur = dummy;auto dfs = [&](this auto&& dfs, TreeNode* root) {if (root == NULL) return;cur->right = root;cur = cur->right;TreeNode* pl = root->left;TreeNode* pr = root->right;cur->left = NULL;cur->right = NULL;dfs(pl);dfs(pr);};dfs(root);}
};先序遍歷模擬
105. 從前序與中序遍歷序列構造二叉樹
class Solution {
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int k = 0;map<int, int> mp;for (int i = 0; i < inorder.size(); i++)mp[inorder[i]] = i;auto dfs = [&](this auto&& dfs, int l, int r) -> TreeNode* {if (l > r) return NULL;TreeNode* root = new TreeNode(preorder[k++]);root->left = dfs(l, mp[root->val] - 1);root->right = dfs(mp[root->val] + 1, r);return root;};return dfs(0, inorder.size() - 1);}
};只要我們在中序遍歷中定位到根節點，那么我們就可以分別知道左子樹和右子樹中的節點數目。由于同一顆子樹的前序遍歷和中序遍歷的長度顯然是相同的，因此我們就可以對應到前序遍歷的結果中，對上述形式中的所有左右括號進行定位。
這樣以來，我們就知道了左子樹的前序遍歷和中序遍歷結果，以及右子樹的前序遍歷和中序遍歷結果，我們就可以遞歸地對構造出左子樹和右子樹，再將這兩顆子樹接到根節點的左右位置。
每次遞歸構造的時候，當前先序遍歷數組的當前第一個節點一定是當前子樹的根節點
437. 路徑總和 III
class Solution {
public:using ll = long long;int pathSum(TreeNode* root, ll targetSum) {map<ll, int> mp;ll ans = 0;mp[0]++;auto dfs = [&](this auto&& dfs, TreeNode* root, ll sum) {if (root == NULL) return;sum += root->val;ans += mp[sum - targetSum];mp[sum]++;dfs(root->left, sum);dfs(root->right, sum);mp[sum]--;};dfs(root, 0);return ans;}
};哈希，dfs表示從根節點開始統計答案，并且結束后清除對map的影響的貢獻
?236. 二叉樹的最近公共祖先
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {unordered_map<TreeNode*, int> dep;unordered_map<TreeNode*, TreeNode*> f;dep[NULL] = 0;auto dfs = [&](this auto&& dfs, TreeNode* root, TreeNode* fa) {if (root == NULL) return;dep[root] = dep[fa] + 1;f[root] = fa;dfs(root->left, root);dfs(root->right, root);};dfs(root, NULL);if (dep[p] < dep[q]) swap(p, q);while (dep[p] != dep[q]) {p = f[p];}if (p == q) return p;while (p != q) {p = f[p];q = f[q];}return p;}
};貪心，先跳到同一層，再往上跳直到相同
?124. 二叉樹中的最大路徑和
class Solution {
public:int maxPathSum(TreeNode* root) {int ans = -1e9;auto dfs = [&](this auto&& dfs, TreeNode* root) -> int {if (root->left && root->right) {int t1 = max(dfs(root->left), 0);int t2 = max(dfs(root->right), 0);int t = t1 + t2 + root->val;ans = max(ans, t);return max(t1, t2) + root->val;}else if (root->left) {int t = max(dfs(root->left), 0) + root->val;ans = max(ans, t);return t;}else if (root->right) {int t = max(dfs(root->right), 0) + root->val;ans = max(ans, t);return t;}else {ans = max(ans, root->val);return root->val;}};dfs(root);return ans;}
};貪心，dfs記錄從root開始，單鏈的最大值
注意分類討論取最大值
函數)
