【二叉树】LC习题看这一篇就够了！（持续更新...）

本文主要是介绍【二叉树】LC习题看这一篇就够了！（持续更新...），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

二叉树的遍历

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/

递归

前序

void traversal(TreeNode* cur, vector<int>& res) {if (cur == NULL) {return;}res.push_back(cur->val);traversal(cur->left, res);traversal(cur->right, res);
}

中序

void traversal(TreeNode* cur, vector<int>& res) {if (cur == NULL) {return;}traversal(cur->left, res);res.push_back(cur->val);traversal(cur->right, res);
}

后序

void traversal(TreeNode* cur, vector<int>& res) {if (cur == NULL) {return;}traversal(cur->left, res);traversal(cur->right, res);res.push_back(cur->val);
}

迭代

前序

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> res;if (root == NULL) {return res;}st.push(root);while (!st.empty()) {TreeNode* node = st.top(); // 中st.pop();res.push_back(node->val);if (node->right) {st.push(node->right); // 右}if (node->left) {st.push(node->left); // 左}}return res;}
};

中序

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> res;TreeNode* cur = root;while (cur != NULL || !st.empty()) {if (cur != NULL) {st.push(cur);cur = cur->left; // 左} else {cur = st.top();st.pop();res.push_back(cur->val); // 中cur = cur->right; // 右}}return res;}
};

后序

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {// 先序是中左右->中右左->倒置(左右中)(后序) stack<TreeNode*> st;vector<int> res;if (root == NULL) {return res;}st.push(root);while (!st.empty()) {TreeNode* node = st.top();st.pop();res.push_back(node->val);if (node->left) {st.push(node->left);}if (node->right) {st.push(node->right);}}reverse(res.begin(), res.end());return res;}
};

144. 二叉树的前序遍历 - 力扣（LeetCode）

94. 二叉树的中序遍历 - 力扣（LeetCode）

145. 二叉树的后序遍历 - 力扣（LeetCode）

589. N 叉树的前序遍历 - 力扣（LeetCode）

590. N 叉树的后序遍历 - 力扣（LeetCode）

606 根据二叉树创建字符串

606. 根据二叉树创建字符串 - 力扣（LeetCode）

给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。

空节点使用一对空括号对 "()" 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

示例 1：

输入：root = [1,2,3,4]
输出："1(2(4))(3)"
解释：初步转化后得到 "1(2(4)())(3()())" ，但省略所有不必要的空括号对后，字符串应该是"1(2(4))(3)" 。

示例 2：

输入：root = [1,2,3,null,4]
输出："1(2()(4))(3)"
解释：和第一个示例类似，但是无法省略第一个空括号对，否则会破坏输入与输出一一映射的关系。

提示：

树中节点的数目范围是 [1, 104]
-1000 <= Node.val <= 1000

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:string tree2str(TreeNode* root) {if (!root) return "";string s = to_string(root->val);if (root->left) {s += "(" + tree2str(root->left) + ")";}if (root->right) {if (!root->left) {s += "()";}s += "(" + tree2str(root->right) + ")";}return s;}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {private StringBuilder sb = new StringBuilder();public String tree2str(TreeNode root) {dfs(root);return sb.substring(1, sb.length() - 1);}public void dfs(TreeNode root) {sb.append("(");sb.append(root.val);if (root.left != null) {dfs(root.left);}if (root.right != null) {if (root.left == null) {sb.append("()");}dfs(root.right);}sb.append(")");}
}

102 二叉树的层序遍历

102. 二叉树的层序遍历 - 力扣（LeetCode）

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> ans;queue<TreeNode*> q;if (!root) {return ans;}q.push(root);while (!q.empty()) {vector<int> levelList;int size = q.size();for (int i = 0; i < size; i++) {TreeNode* node = q.front();q.pop();levelList.push_back(node->val);if (node->left) {q.push(node->left);}if (node->right) {q.push(node->right);}}ans.push_back(levelList);}return ans;}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<List<Integer>> levelOrder(TreeNode root) {if (root == null) {return List.of();}List<List<Integer>> ans = new ArrayList<>();Queue<TreeNode> q = new ArrayDeque<>();q.add(root);while (!q.isEmpty()) {int n = q.size();List<Integer> vals = new ArrayList<>(n);while (n-- > 0) {TreeNode node = q.poll();//删除队头的元素vals.add(node.val);if (node.left != null) q.add(node.left);if (node.right != null) q.add(node.right);}ans.add(vals);}return ans;}
}

107 二叉树的层序遍历Ⅱ

107. 二叉树的层序遍历 II - 力扣（LeetCode）

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<vector<int>> levelOrderBottom(TreeNode* root) {vector<vector<int>> ans;if (!root) {return ans;}queue<TreeNode*> q;stack<vector<int>> st;q.push(root);while (!q.empty()) {vector<int> levelList;int size = q.size();for (int i = 0; i < size; i++) {TreeNode* node = q.front();q.pop();levelList.push_back(node->val);if (node->left) {q.push(node->left);}if (node->right) {q.push(node->right);}}st.push(levelList);}while (!st.empty()) {vector<int> v = st.top();ans.push_back(v);st.pop();}return ans;}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<List<Integer>> levelOrderBottom(TreeNode root) {if (root == null) {return List.of();}List<List<Integer>> ans = new ArrayList<>();Deque<TreeNode> d = new ArrayDeque<>();d.add(root);while (!d.isEmpty()) {int size = d.size();List<Integer> levelList = new ArrayList<>();while (size-- > 0) {TreeNode node = d.poll();levelList.add(node.val);if (node.left != null) d.add(node.left);if (node.right != null) d.add(node.right);}ans.add(levelList);}Collections.reverse(ans);return ans;}
}

103 二叉树的锯齿形层序遍历

103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode）

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

树中节点数目在范围 [0, 2000] 内
-100 <= Node.val <= 100

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<vector<int>> zigzagLevelOrder(TreeNode* root) {vector<vector<int>> ans;if (!root) {return ans;}queue<TreeNode*> q;q.push(root);bool flag = true; // 记录从左到右还是从右到左while (!q.empty()) {deque<int> levelList;int size = q.size();for (int i = 0; i < size; i++) {TreeNode* node = q.front();q.pop();if (flag) {levelList.push_back(node->val);} else {levelList.push_front(node->val);}if (node->left) {q.push(node->left);}if (node->right) {q.push(node->right);}}ans.push_back(vector<int>{levelList.begin(), levelList.end()});flag = !flag;}return ans;}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {if (root == null) {return List.of();}List<List<Integer>> ans = new ArrayList<>();List<TreeNode> cur = new ArrayList<>();boolean even = false;cur.add(root);while (!cur.isEmpty()) {List<TreeNode> nxt = new ArrayList<>(cur.size());List<Integer> vals = new ArrayList<>();for (TreeNode node : cur) {vals.add(node.val);if (node.left != null) nxt.add(node.left);if (node.right != null) nxt.add(node.right);}cur = nxt;if (even) Collections.reverse(vals);ans.add(vals);even = !even;}return ans;}
}

623 在二叉树中增加一行

623. 在二叉树中增加一行 - 力扣（LeetCode）

给定一个二叉树的根 root 和两个整数 val 和 depth ，在给定的深度 depth 处添加一个值为 val 的节点行。

注意，根节点 root 位于深度 1 。

加法规则如下:

给定整数 depth，对于深度为 depth - 1 的每个非空树节点 cur ，创建两个值为 val 的树节点作为 cur 的左子树根和右子树根。
cur 原来的左子树应该是新的左子树根的左子树。
cur 原来的右子树应该是新的右子树根的右子树。
如果 depth == 1 意味着 depth - 1 根本没有深度，那么创建一个树节点，值 val 作为整个原始树的新根，而原始树就是新根的左子树。

示例 1:

输入: root = [4,2,6,3,1,5], val = 1, depth = 2
输出: [4,1,1,2,null,null,6,3,1,5]

示例 2:

输入: root = [4,2,null,3,1], val = 1, depth = 3
输出:  [4,2,null,1,1,3,null,null,1]

提示:

节点数在 [1, 104] 范围内
树的深度在 [1, 104]范围内
-100 <= Node.val <= 100
-105 <= val <= 105
1 <= depth <= the depth of tree + 1

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* addOneRow(TreeNode* root, int val, int depth) {if (depth == 1) return new TreeNode(val, root, nullptr);queue<TreeNode*> q;q.push(root);int cur = 1;while (!q.empty()) {int size = q.size();while(size-- > 0) {TreeNode* t = q.front();q.pop();if (cur == depth - 1) {TreeNode* a = new TreeNode(val);TreeNode* b = new TreeNode(val);a->left = t->left;b->right = t->right;t->left = a;t->right = b;} else {if (t->left) q.push(t->left);if (t->right) q.push(t->right);}}cur++;}return root;}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode addOneRow(TreeNode root, int val, int depth) {if (depth == 1) return new TreeNode(val, root, null);Deque<TreeNode> d = new ArrayDeque<>();d.addLast(root);int cur = 1;while (!d.isEmpty()) {int size = d.size();while (size-- > 0) {TreeNode t = d.pollFirst();if (cur == depth - 1) {TreeNode a = new TreeNode(val), b = new TreeNode(val);a.left = t.left;b.right = t.right;t.left = a;t.right = b;} else {if (t.left != null) d.addLast(t.left);if (t.right != null) d.addLast(t.right);}}cur++;}return root;}
}

987 二叉树的垂序遍历

987. 二叉树的垂序遍历 - 力扣（LeetCode）

给你二叉树的根结点 root ，请你设计算法计算二叉树的 垂序遍历 序列。

对位于 (row, col) 的每个结点而言，其左右子结点分别位于 (row + 1, col - 1) 和 (row + 1, col + 1) 。树的根结点位于 (0, 0) 。

二叉树的 垂序遍历 从最左边的列开始直到最右边的列结束，按列索引每一列上的所有结点，形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点，则按结点的值从小到大进行排序。

返回二叉树的 垂序遍历 序列。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[9],[3,15],[20],[7]]
解释：
列 -1 ：只有结点 9 在此列中。
列  0 ：只有结点 3 和 15 在此列中，按从上到下顺序。
列  1 ：只有结点 20 在此列中。
列  2 ：只有结点 7 在此列中。

示例 2：

输入：root = [1,2,3,4,5,6,7]
输出：[[4],[2],[1,5,6],[3],[7]]
解释：
列 -2 ：只有结点 4 在此列中。
列 -1 ：只有结点 2 在此列中。
列  0 ：结点 1 、5 和 6 都在此列中。1 在上面，所以它出现在前面。5 和 6 位置都是 (2, 0) ，所以按值从小到大排序，5 在 6 的前面。
列  1 ：只有结点 3 在此列中。
列  2 ：只有结点 7 在此列中。

示例 3：

输入：root = [1,2,3,4,6,5,7]
输出：[[4],[2],[1,5,6],[3],[7]]
解释：
这个示例实际上与示例 2 完全相同，只是结点 5 和 6 在树中的位置发生了交换。
因为 5 和 6 的位置仍然相同，所以答案保持不变，仍然按值从小到大排序。

提示：

树中结点数目总数在范围 [1, 1000] 内
0 <= Node.val <= 1000

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<vector<int>> verticalTraversal(TreeNode* root) {vector<tuple<int, int, int>> nodes;function<void(TreeNode*, int, int)> dfs = [&](TreeNode* node, int row, int col) {if (!node) {return;}nodes.emplace_back(col, row, node->val);dfs(node->left, row + 1, col - 1);dfs(node->right, row + 1, col + 1);};dfs(root, 0, 0);sort(nodes.begin(), nodes.end());vector<vector<int>> ans;int lastcol = INT_MIN;for (const auto& [col, row, val] : nodes) {if (col != lastcol) {lastcol = col;ans.emplace_back();}ans.back().push_back(val);}return ans;}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<List<Integer>> verticalTraversal(TreeNode root) {List<int[]> data = new ArrayList<>();dfs(root, 0, 0, data);List<List<Integer>> ans = new ArrayList<>();data.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] != b[1] ? a[1] - b[1] : a[2] - b[2]);int last_col = Integer.MIN_VALUE;for (var d : data) {if (d[0] != last_col) {last_col = d[0];ans.add(new ArrayList<>());}ans.get(ans.size() - 1).add(d[2]);}return ans;}public void dfs(TreeNode node, int row, int col, List<int[]> data) {if (node == null) {return;}data.add(new int[]{col, row, node.val});dfs(node.left, row + 1, col - 1, data);dfs(node.right, row + 1, col + 1, data);}
}

236 二叉树的最近公共祖先

236. 二叉树的最近公共祖先 - 力扣（LeetCode）

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 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 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

输入：root = [1,2], p = 1, q = 2
输出：1

提示：

树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
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 == nullptr || 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;}return left ? left : right;}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {//无法确定遍历后p q的位置 可能遍历到空节点if (root == null || root == p || root == q) {return root;}TreeNode left = lowestCommonAncestor(root.left,p,q);TreeNode right = lowestCommonAncestor(root.right,p,q);if (left != null && right != null) {return root;}return left != null ? left : right;}
}

993 二叉树的堂兄弟节点

993. 二叉树的堂兄弟节点 - 力扣（LeetCode）

在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。

如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。

我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。

只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。

示例 1：

输入：root = [1,2,3,4], x = 4, y = 3
输出：false

示例 2：

输入：root = [1,2,3,null,4,null,5], x = 5, y = 4
输出：true

示例 3：

输入：root = [1,2,3,null,4], x = 2, y = 3
输出：false

提示：

二叉树的节点数介于 2 到 100 之间。
每个节点的值都是唯一的、范围为 1 到 100 的整数。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool isCousins(TreeNode* root, int x, int y) {int depth = 0;TreeNode* father = nullptr;function<bool(TreeNode*, TreeNode*, int)> dfs = [&](TreeNode* node, TreeNode* fa, int d) {if (!node) {return false;}if (node->val == x || node->val == y) {if (depth > 0) {return depth == d && father != fa;}depth = d;father = fa;}return dfs(node->left, node, d + 1) || dfs(node->right, node, d + 1);};return dfs(root, nullptr, 1);}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int depth;TreeNode father;public boolean isCousins(TreeNode root, int x, int y) {return dfs(root, null, 1, x, y);}public boolean dfs(TreeNode node, TreeNode fa, int d, int x, int y) {if (node == null) {return false;}if (node.val == x || node.val == y) {if (depth > 0) {// 之前找到 x y 其中之一return depth == d && father != fa;}// 没找到depth = d;father = fa;}return dfs(node.left, node, d + 1, x, y) || dfs(node.right, node, d + 1, x, y);}
}

2641 二叉树的堂兄弟节点Ⅱ

2641. 二叉树的堂兄弟节点 II - 力扣（LeetCode）

给你一棵二叉树的根 root ，请你将每个节点的值替换成该节点的所有 堂兄弟节点值的和 。

如果两个节点在树中有相同的深度且它们的父节点不同，那么它们互为 堂兄弟 。

请你返回修改值之后，树的根 root 。

注意，一个节点的深度指的是从树根节点到这个节点经过的边数。

示例 1：

输入：root = [5,4,9,1,10,null,7]
输出：[0,0,0,7,7,null,11]
解释：上图展示了初始的二叉树和修改每个节点的值之后的二叉树。
- 值为 5 的节点没有堂兄弟，所以值修改为 0 。
- 值为 4 的节点没有堂兄弟，所以值修改为 0 。
- 值为 9 的节点没有堂兄弟，所以值修改为 0 。
- 值为 1 的节点有一个堂兄弟，值为 7 ，所以值修改为 7 。
- 值为 10 的节点有一个堂兄弟，值为 7 ，所以值修改为 7 。
- 值为 7 的节点有两个堂兄弟，值分别为 1 和 10 ，所以值修改为 11 。

示例 2：

输入：root = [3,1,2]
输出：[0,0,0]
解释：上图展示了初始的二叉树和修改每个节点的值之后的二叉树。
- 值为 3 的节点没有堂兄弟，所以值修改为 0 。
- 值为 1 的节点没有堂兄弟，所以值修改为 0 。
- 值为 2 的节点没有堂兄弟，所以值修改为 0 。

提示：

树中节点数目的范围是 [1, 105] 。
1 <= Node.val <= 104

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* replaceValueInTree(TreeNode* root) {root->val = 0;vector<TreeNode*> q;q.push_back(root);while (!q.empty()) {vector<TreeNode*> nxt;int next_level_sum = 0;for (auto node : q) {if (node->left) {nxt.push_back(node->left);next_level_sum += node->left->val;}if (node->right) {nxt.push_back(node->right);next_level_sum += node->right->val;}}for (auto node : q) {int children_sum = (node->left ? node->left->val : 0) + (node->right ? node->right->val : 0);if (node->left) {node->left->val = next_level_sum - children_sum;}if (node->right) {node->right->val = next_level_sum - children_sum;}}q = move(nxt);}return root;}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode replaceValueInTree(TreeNode root) {root.val = 0;List<TreeNode> q = new ArrayList<>();q.add(root);while (!q.isEmpty()) {List<TreeNode> nxt = new ArrayList<>();int next_level_sum = 0;for (var node : q) {if (node.left != null) {nxt.add(node.left);next_level_sum += node.left.val;}if (node.right != null) {nxt.add(node.right);next_level_sum += node.right.val;}}for (var node : q) {int children_sum = (node.left != null ? node.left.val : 0) + (node.right != null ? node.right.val : 0);if (node.left != null) {node.left.val = next_level_sum - children_sum;}if (node.right != null) {node.right.val = next_level_sum - children_sum;}}q = nxt;}return root;}
}

105 从前序与中序遍历序列构造二叉树

105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

提示:

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均 无重复 元素
inorder 均出现在 preorder
preorder 保证为二叉树的前序遍历序列
inorder 保证为二叉树的中序遍历序列

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {//第一种写法// if (preorder.empty()) {//     return nullptr;// }// int left_size = ranges::find(inorder, preorder[0]) - inorder.begin(); // vector<int> pre1(preorder.begin() + 1, preorder.begin() + 1 + left_size);// vector<int> pre2(preorder.begin() + 1 + left_size, preorder.end());// vector<int> in1(inorder.begin(), inorder.begin() + left_size);// vector<int> in2(inorder.begin() + 1 + left_size, inorder.end());// TreeNode *left = buildTree(pre1, in1);// TreeNode *right = buildTree(pre2, in2);// return new TreeNode(preorder[0], left, right);//哈希表优化版本int n = preorder.size();unordered_map<int, int> index;for (int i = 0; i < n; i++) {index[inorder[i]] = i;}function<TreeNode*(int, int, int, int)> dfs = [&](int pre_l, int pre_r, int in_l, int in_r) -> TreeNode* {if (pre_l == pre_r) {return nullptr;}int size = index[preorder[pre_l]] - in_l;TreeNode* left = dfs(pre_l + 1, pre_l + 1 + size, in_l, in_l + size);TreeNode* right = dfs(pre_l + 1 + size, pre_r, in_l + 1 + size, in_r);return new TreeNode(preorder[pre_l], left, right);};return dfs(0, n, 0, n);}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {Map<Integer, Integer> index = new HashMap<>();public TreeNode buildTree(int[] preorder, int[] inorder) {int n = preorder.length;for (int i = 0; i < n; i++) {index.put(inorder[i], i);}return dfs(preorder, 0, n, inorder, 0, n);}public TreeNode dfs(int[] preorder, int preL, int preR, int[] inorder, int inL, int inR) {if (preL == preR) {return null;}int size = index.get(preorder[preL]) - inL;TreeNode left = dfs(preorder, preL + 1, preL + 1 + size, inorder, inL, inL + size);TreeNode right = dfs(preorder, preL + 1 + size, preR, inorder, inL + size + 1, inR);return new TreeNode(preorder[preL], left, right);}
}

106 从中序与后序遍历序列构造二叉树

106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例 1:

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

示例 2:

输入：inorder = [-1], postorder = [-1]
输出：[-1]

提示:

1 <= inorder.length <= 3000
postorder.length == inorder.length
-3000 <= inorder[i], postorder[i] <= 3000
inorder 和 postorder 都由不同的值组成
postorder 中每一个值都在 inorder 中
inorder 保证是树的中序遍历
postorder 保证是树的后序遍历

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {//第一种写法// if (postorder.empty()) {//     return nullptr;// }// int size = ranges::find(inorder, postorder[postorder.size() - 1]) - inorder.begin();// vector<int> in1(inorder.begin(), inorder.begin() + size);// vector<int> in2(inorder.begin() + 1 + size, inorder.end());// vector<int> post1(postorder.begin(), postorder.begin() + size);// vector<int> post2(postorder.begin() + size, postorder.end() - 1);// TreeNode* left = buildTree(in1, post1);// TreeNode* right = buildTree(in2, post2);// return new TreeNode(postorder[postorder.size() - 1], left, right);//哈希表优化版本int n = postorder.size();unordered_map<int, int> index;for (int i = 0; i < n; i++) {index[inorder[i]] = i;}function<TreeNode*(int, int, int, int)> dfs = [&](int post_l, int post_r, int in_l, int in_r) -> TreeNode* {if (post_l == post_r) {return nullptr;}int size = index[postorder[post_r - 1]] - in_l;TreeNode* left = dfs(post_l, post_l + size, in_l, in_l + size);TreeNode* right = dfs(post_l + size, post_r - 1, in_l + 1 + size, in_r);return new TreeNode(postorder[post_r - 1], left, right);};return dfs(0, n, 0, n);}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {Map<Integer, Integer> index = new HashMap<>();public TreeNode buildTree(int[] inorder, int[] postorder) {int n = postorder.length;for (int i = 0; i < n; i++) {index.put(inorder[i], i);}return dfs(postorder, 0, n, inorder, 0, n);}public TreeNode dfs(int[] postorder, int postL, int postR, int[] inorder, int inL, int inR) {if (postL == postR) {return null;}int size = index.get(postorder[postR - 1]) - inL;TreeNode left = dfs(postorder, postL, postL+ size, inorder, inL, inL + size);TreeNode right = dfs(postorder, postL + size, postR - 1, inorder, inL + size + 1, inR);return new TreeNode(postorder[postR - 1], left, right);}
}

889 根据前序和后序遍历构造二叉树

889. 根据前序和后序遍历构造二叉树 - 力扣（LeetCode）

给定两个整数数组，preorder 和 postorder ，其中 preorder 是一个具有 无重复 值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树。

如果存在多个答案，您可以返回其中任何一个。

示例 1：

输入：preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
输出：[1,2,3,4,5,6,7]

示例 2:

输入: preorder = [1], postorder = [1]
输出: [1]

提示：

1 <= preorder.length <= 30
1 <= preorder[i] <= preorder.length
preorder 中所有值都不同
postorder.length == preorder.length
1 <= postorder[i] <= postorder.length
postorder 中所有值都不同
保证 preorder 和 postorder 是同一棵二叉树的前序遍历和后序遍历

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {//第一种// if (preorder.empty()) {//     return nullptr;// }// if (preorder.size() == 1) {//     return new TreeNode(preorder[0]);// }// int size = ranges::find(postorder, preorder[1]) - postorder.begin() + 1;// vector<int> pre1(preorder.begin() + 1, preorder.begin() + 1 + size);// vector<int> pre2(preorder.begin() + 1 + size, preorder.end());// vector<int> post1(postorder.begin(), postorder.begin() + size);// vector<int> post2(postorder.begin() + size, postorder.end() - 1);// TreeNode* left = constructFromPrePost(pre1, post1);// TreeNode* right = constructFromPrePost(pre2, post2);// return new TreeNode(preorder[0], left, right);//哈希表优化版本int n = postorder.size();unordered_map<int, int> index;for (int i = 0; i < n; i++) {index[postorder[i]] = i;}function<TreeNode*(int, int, int, int)> dfs = [&](int pre_l, int pre_r, int post_l, int post_r) -> TreeNode* {if (pre_l == pre_r) {return nullptr;}if (pre_l + 1 == pre_r) {return new TreeNode(preorder[pre_l]);}int size = index[preorder[pre_l + 1]] - post_l + 1;TreeNode* left = dfs(pre_l + 1, pre_l + 1 + size, post_l, post_l + size);TreeNode* right = dfs(pre_l + 1 + size, pre_r, post_l + size, post_r - 1);return new TreeNode(preorder[pre_l], left, right);};return dfs(0, n, 0, n);}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {int n = preorder.length;int[] index = new int[n + 1];for (int i = 0; i < n; i++) {index[postorder[i]] = i;}return dfs(postorder, 0, n, preorder, 0, n, index);}public TreeNode dfs(int[] postorder, int postL, int postR, int[] preorder, int preL, int preR, int[] index) {if (preL == preR) {return null;}if (preL + 1 == preR) {return new TreeNode(preorder[preL]);}int size = index[preorder[preL + 1]] - postL + 1;TreeNode left = dfs(postorder, postL, postL+ size, preorder, preL + 1, preL + 1 + size, index);TreeNode right = dfs(postorder, postL + size, postR - 1, preorder, preL + size + 1, preR, index);return new TreeNode(preorder[preL], left, right);}
}

331 验证二叉树的前序序列化

331. 验证二叉树的前序序列化 - 力扣（LeetCode）

序列化二叉树的一种方法是使用 前序遍历 。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。

例如，上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一个空节点。

给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。

保证每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 '#' 。

你可以认为输入格式总是有效的

例如它永远不会包含两个连续的逗号，比如 "1,,3" 。

**注意：**不允许重建树。

示例 1:

输入: preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"
输出: true

示例 2:

输入: preorder = "1,#"
输出: false

示例 3:

输入: preorder = "9,#,#,1"
输出: false

提示:

1 <= preorder.length <= 104
preorder 由以逗号 “，” 分隔的 [0,100] 范围内的整数和 “#” 组成

class Solution {
public://每一个非空节点都对应了 2 个出度，空节点都对应了 0 个出度；除了根节点，每个节点都有一个入度//设 in 为入度个数  out 为出度个数  m 为非空节点个数  n 为空节点个数//可以得到 m >= n   in <= m + n - 1   out <= 2 * m//遍历过程中每遇到一个「非空节点」就增加两个「出度」和一个「入度」，每遇到一个「空节点」只增加一个「入度」。//而不管每个「非空节点」是否真实对应两个子节点//可以得到 m >= n   in = m + n - 1   out = 2 * mvector<string> spilt(string &preorder) {stringstream ss(preorder);string temp;vector<string> ans;while (getline(ss, temp, ',')) {ans.push_back(temp);}return ans;}bool isValidSerialization(string preorder) {vector<string> s = spilt(preorder);int n = s.size();int in = 0, out = 0;for (int i = 0; i < n; i++) {if (s[i] != "#") out += 2;if (i != 0) in++;if (i != n - 1 && out <= in) return false;}return in == out;}
};

class Solution {public boolean isValidSerialization(String preorder) {String[] s = preorder.split(",");int n = s.length;int in = 0, out = 0;for (int i = 0; i < n; i++) {if (!s[i].equals("#")) out += 2;if (i != 0) in++;if (i != n - 1 && out <= in) return false;}return in == out;}
}

2583 二叉树中的第K大层和

2583. 二叉树中的第 K 大层和 - 力扣（LeetCode）

给你一棵二叉树的根节点 root 和一个正整数 k 。

树中的层和是指 同一层 上节点值的总和。

返回树中第 k 大的层和（不一定不同）。如果树少于 k 层，则返回 -1 。

注意，如果两个节点与根节点的距离相同，则认为它们在同一层。

示例 1：

输入：root = [5,8,9,2,1,3,7,4,6], k = 2
输出：13
解释：树中每一层的层和分别是：
- Level 1: 5
- Level 2: 8 + 9 = 17
- Level 3: 2 + 1 + 3 + 7 = 13
- Level 4: 4 + 6 = 10
第 2 大的层和等于 13 。

示例 2：

输入：root = [1,2,null,3], k = 1
输出：3
解释：最大的层和是 3 。

提示：

树中的节点数为 n
2 <= n <= 105
1 <= Node.val <= 106
1 <= k <= n

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:long long kthLargestLevelSum(TreeNode* root, int k) {vector<long long> ans;queue<TreeNode*> q;q.push(root);while (!q.empty()) {long long levelVal = 0;int size = q.size();for (int i = 0; i < size; i++) {TreeNode* node = q.front();q.pop();levelVal += node->val;if (node->left) {q.push(node->left);}if (node->right) {q.push(node->right);}}ans.push_back(levelVal);}int n = ans.size();if (k > n) {return -1;}ranges::sort(ans);return ans[n - k];}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public long kthLargestLevelSum(TreeNode root, int k) {List<Long> ans = new ArrayList<>();Deque<TreeNode> q = new ArrayDeque<>();q.add(root);while (!q.isEmpty()) {long levelVal = 0;int size = q.size();for (int i = 0; i < size; i++) {TreeNode node = q.poll();levelVal += node.val;if (node.left != null) {q.add(node.left);}if (node.right != null) {q.add(node.right);}}ans.add(levelVal);}int n = ans.size();if (k > n) {return -1;}Collections.sort(ans);return ans.get(n - k);}
}

257 二叉树的所有路径

257. 二叉树的所有路径 - 力扣（LeetCode）

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]

示例 2：

输入：root = [1]
输出：["1"]

提示：

树中节点的数目在范围 [1, 100] 内
-100 <= Node.val <= 100

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<string> binaryTreePaths(TreeNode* root) {vector<string> res;if (!root) return res;if (!root->left && !root->right) {res.push_back(to_string(root->val));return res;}for (auto path : binaryTreePaths(root->left)) {res.push_back(to_string(root->val) + "->" + path);}for (auto path : binaryTreePaths(root->right)) {res.push_back(to_string(root->val) + "->" + path);}return res;}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<String> binaryTreePaths(TreeNode root) {if (root == null) {return new ArrayList();}List<String> left = binaryTreePaths(root.left);List<String> right = binaryTreePaths(root.right);List<String> res = new ArrayList<>();if (root.left == null && root.right == null) {res.add(root.val + "");return res;}for (int i = 0; i < left.size(); i++) {res.add(root.val + "->" + left.get(i));}for (int i = 0; i < right.size(); i++) {res.add(root.val + "->" + right.get(i));}return res;}
}

543 二叉树的直径

543. 二叉树的直径 - 力扣（LeetCode）

给你一棵二叉树的根节点，返回该树的直径。

二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的长度由它们之间边数表示。

示例 1：

输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。

示例 2：

输入：root = [1,2]
输出：1

提示：

树中节点数目在范围 [1, 104] 内
-100 <= Node.val <= 100

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int ans = 0;int dfs(TreeNode* root) {if (root == nullptr) {return -1;}int left = dfs(root->left) + 1;int right = dfs(root->right) + 1;ans = max(ans, left + right);return max(left, right);}int diameterOfBinaryTree(TreeNode* root) {dfs(root);return ans;}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {private int ans; public int diameterOfBinaryTree(TreeNode root) {dfs(root);return ans;}private int dfs(TreeNode root) {if (root == null) {return -1;//返回-1 下面+1变成了0}int l_len = dfs(root.left) + 1;//左子树最大链长+1int r_len = dfs(root.right) + 1;//右子树最大链长+1ans = Math.max(ans, l_len + r_len);return Math.max(l_len, r_len);}
}

112 路径总和

112. 路径总和 - 力扣（LeetCode）

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。

示例 2：

输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。

示例 3：

输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。

提示：

树中节点的数目在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool hasPathSum(TreeNode* root, int targetSum) {if (!root) {return false;}if (!root->left && !root->right) {return root->val == targetSum;}return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val);}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {if (root == null) {return false;}if (root.left == null && root.right == null) {return targetSum == root.val;} return hasPathSum(root.left,targetSum - root.val) || hasPathSum(root.right,targetSum - root.val);}
}

113 路径总和Ⅱ

113. 路径总和 II - 力扣（LeetCode）

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

示例 2：

输入：root = [1,2,3], targetSum = 5
输出：[]

示例 3：

输入：root = [1,2], targetSum = 0
输出：[]

提示：

树中节点总数在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<vector<int>> res;vector<int> path;void dfs(TreeNode* root, int count) {if (!root->left && !root->right && count == 0) {res.push_back(path);return;}if (!root->left && !root->right) return;if (root->left) { //左path.push_back(root->left->val);count -= root->left->val;dfs(root->left, count); // 递归count += root->left->val; // 恢复现场path.pop_back(); // 恢复现场}if (root->right) { //右path.push_back(root->right->val);count -= root->right->val;dfs(root->right, count); // 递归count += root->right->val; // 恢复现场path.pop_back(); // 恢复现场}return;}vector<vector<int>> pathSum(TreeNode* root, int targetSum) {res.clear();path.clear();if (!root) return res;path.push_back(root->val);dfs(root, targetSum - root->val);return res;}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {private List<List<Integer>> res;private List<Integer> path;public List<List<Integer>> pathSum(TreeNode root, int targetSum) {res = new ArrayList<>();path = new ArrayList<>();if (root == null) return res;path.add(root.val);dfs(root, targetSum - root.val);return res;}public void dfs(TreeNode root, int sum) {if (root.left == null && root.right == null && sum == 0) {res.add(new ArrayList<>(path));return;}if (root.left == null && root.right == null) return;if (root.left != null) {path.add(root.left.val);sum -= root.left.val;dfs(root.left, sum);sum += root.left.val;path.remove(path.size() - 1);}if (root.right != null) {path.add(root.right.val);sum -= root.right.val;dfs(root.right, sum);sum += root.right.val;path.remove(path.size() - 1);}return;}
}

437 路径总和Ⅲ

437. 路径总和 III - 力扣（LeetCode）

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

示例 1：

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。

示例 2：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3

提示:

二叉树的节点个数的范围是 [0,1000]
-109 <= Node.val <= 109
-1000 <= targetSum <= 1000

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int ans, t;void dfs2(TreeNode* root, long long val) {if (val == t) ans++;if (root->left) dfs2(root->left, val + root->left->val);if (root->right) dfs2(root->right, val + root->right->val);}void dfs1(TreeNode* root) {if (!root) return;dfs2(root, root->val);dfs1(root->left);dfs1(root->right);}int pathSum(TreeNode* root, int targetSum) {t = targetSum;dfs1(root);return ans;}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {private int ans;private int t;public int pathSum(TreeNode root, int targetSum) {t = targetSum;dfs1(root);return ans;}public void dfs1(TreeNode root) {if (root == null) {return;}dfs2(root, root.val);dfs1(root.left);dfs1(root.right);}public void dfs2(TreeNode root, long val) {if (val == t) ans++;if (root.left != null) dfs2(root.left, val + root.left.val);if (root.right != null) dfs2(root.right, val + root.right.val);}
}

114 二叉树展开为链表

114. 二叉树展开为链表 - 力扣（LeetCode）

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例 1：

输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [0]
输出：[0]

提示：

树中结点数在范围 [0, 2000] 内
-100 <= Node.val <= 100

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:void flatten(TreeNode* root) {TreeNode* cur = root;while (cur) {if (cur->left) {TreeNode* nxt = cur->left;TreeNode* pre = nxt;while (pre->right) {pre = pre->right;}pre->right = cur->right;cur->left = nullptr;cur->right = nxt;}cur = cur->right;}}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public void flatten(TreeNode root) {TreeNode cur = root;while (cur != null) {if (cur.left != null) {TreeNode nxt = cur.left;TreeNode pre = nxt;while (pre.right != null) {pre = pre.right;}pre.right = cur.right;cur.left = null;cur.right = nxt;}cur = cur.right;}}
}

124 二叉树中的最大路径和

124. 二叉树中的最大路径和 - 力扣（LeetCode）

二叉树中的路径被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例 1：

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

提示：

树中节点数目范围是 [1, 3 * 104]
-1000 <= Node.val <= 1000

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int ans = INT_MIN;int dfs(TreeNode* root) {if (!root) return 0;int l_val = dfs(root->left);int r_val = dfs(root->right);ans = max(ans, l_val + r_val + root->val);return max(max(l_val, r_val) + root->val, 0);}int maxPathSum(TreeNode* root) {dfs(root);return ans;}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {private int ans = Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {dfs(root);return ans;}private int dfs(TreeNode root) {if (root == null) {return 0;//没有结点 和为0}int l_val = dfs(root.left);int r_val = dfs(root.right);ans = Math.max(ans, l_val + r_val + root.val);return Math.max(Math.max(l_val, r_val) + root.val, 0);//负数不选}
}

129 求根节点到叶节点数字之和

129. 求根节点到叶节点数字之和 - 力扣（LeetCode）

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。

每条从根节点到叶节点的路径都代表一个数字：

例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。

计算从根节点到叶节点生成的 所有数字之和 。

叶节点 是指没有子节点的节点。

示例 1：

输入：root = [1,2,3]
输出：25
解释：
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此，数字总和 = 12 + 13 = 25

示例 2：

输入：root = [4,9,0,5,1]
输出：1026
解释：
从根到叶子节点路径 4->9->5 代表数字 495
从根到叶子节点路径 4->9->1 代表数字 491
从根到叶子节点路径 4->0 代表数字 40
因此，数字总和 = 495 + 491 + 40 = 1026

提示：

树中节点的数目在范围 [1, 1000] 内
0 <= Node.val <= 9
树的深度不超过 10

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int sumRoot(TreeNode* root, int i) {if (!root) return 0;int temp = root->val + i * 10;if (!root->left && !root->right) return temp;return sumRoot(root->left, temp) + sumRoot(root->right, temp);}int sumNumbers(TreeNode* root) {return sumRoot(root, 0);}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int sumNumbers(TreeNode root) {return sumRoot(root,0);}public int sumRoot(TreeNode root, int i) {if (root == null) {return 0;}int temp = i * 10 + root.val;if (root.right == null && root.left == null) {return temp;}return sumRoot(root.left,temp) + sumRoot(root.right,temp);}
}

199 二叉树的右视图

199. 二叉树的右视图 - 力扣（LeetCode）

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例 1:

输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

示例 2:

输入: [1,null,3]
输出: [1,3]

示例 3:

输入: []
输出: []

提示:

二叉树的节点个数的范围是 [0,100]
-100 <= Node.val <= 100

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<int> ans;void dfs(TreeNode* root, int depth) {if (!root) return;if (depth == ans.size()) {ans.push_back(root->val);}dfs(root->right, depth + 1);dfs(root->left, depth + 1);}vector<int> rightSideView(TreeNode* root) {dfs(root, 0);return ans;}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {List<Integer> ans = new ArrayList<>();public List<Integer> rightSideView(TreeNode root) {bfs(root, 0);return ans;}private void bfs(TreeNode root, int depth) {if (root == null) {return;}if (depth == ans.size()) {ans.add(root.val);}//递归完一层 depth加一bfs(root.right, depth + 1);bfs(root.left, depth + 1);}
}

508 出现次数最多的子树元素和

508. 出现次数最多的子树元素和 - 力扣（LeetCode）

给你一个二叉树的根结点 root ，请返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。

一个结点的 「子树元素和」 定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。

示例 1：

输入: root = [5,2,-3]
输出: [2,-3,4]

示例 2：

输入: root = [5,2,-5]
输出: [2]

提示:

节点数在 [1, 104] 范围内
-105 <= Node.val <= 105

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int mx = 0;unordered_map<int, int> map;int dfs(TreeNode* root) {if (!root) return 0;int sum = root->val + dfs(root->left) + dfs(root->right);map[sum]++;mx = max(mx, map[sum]);return sum;}vector<int> findFrequentTreeSum(TreeNode* root) {dfs(root);vector<int> ans;for (auto it = map.begin(); it != map.end(); it++) {if (it->second == mx) {ans.push_back(it->first);}}return ans;}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {private Map<Integer, Integer> map = new HashMap<>();private int max = 0;public int[] findFrequentTreeSum(TreeNode root) {dfs(root);List<Integer> list = new ArrayList<>();for (int k : map.keySet()) {if (map.get(k) == max) {list.add(k);}}int n = list.size();int[] ans = new int[n];for (int i = 0; i < n; i++) {ans[i] = list.get(i);}return ans;}private int dfs(TreeNode root) {if (root == null) return 0;int sum = root.val + dfs(root.left) + dfs(root.right);map.put(sum, map.getOrDefault(sum, 0) + 1);max = Math.max(max, map.get(sum));return sum;}
}

513 找树左下角的值

513. 找树左下角的值 - 力扣（LeetCode）

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层最左边 节点的值。

假设二叉树中至少有一个节点。

示例 1:

输入: root = [2,1,3]
输出: 1

示例 2:

输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7

提示:

二叉树的节点个数的范围是 [1,104]
-231 <= Node.val <= 231 - 1

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int findBottomLeftValue(TreeNode* root) {queue<TreeNode*> q;TreeNode* node;q.push(root);while (!q.empty()) {node = q.front();q.pop();if (node->right) q.push(node->right);if (node->left) q.push(node->left);}return node->val;}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int findBottomLeftValue(TreeNode root) {TreeNode node = root;Queue<TreeNode> q = new ArrayDeque<>();q.add(root);while (!q.isEmpty()) {node = q.poll();if (node.right != null) q.add(node.right);if (node.left != null) q.add(node.left);}return node.val;}
}

515 在每个树行中找最大值

515. 在每个树行中找最大值 - 力扣（LeetCode）

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

示例1：

输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]

示例2：

输入: root = [1,2,3]
输出: [1,3]

提示：

二叉树的节点个数的范围是 [0,104]
-231 <= Node.val <= 231 - 1

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<int> largestValues(TreeNode* root) {if (!root) {return {};}vector<int> ans;queue<TreeNode*> q;q.push(root);while (!q.empty()) {int mx = INT_MIN;int n = q.size();while (n > 0) {n--;TreeNode* node = q.front();q.pop();mx = max(mx, node->val);if (node->left) q.push(node->left);if (node->right) q.push(node->right); }ans.push_back(mx);}return ans;}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Integer> largestValues(TreeNode root) {if (root == null) {return List.of();}Queue<TreeNode> q = new ArrayDeque<>();List<Integer> ans = new ArrayList<>();TreeNode node;q.add(root);while (!q.isEmpty()) {int n = q.size();int max = Integer.MIN_VALUE;while (n > 0) {n--;node = q.poll();max = Math.max(max, node.val);if (node.left != null) q.add(node.left);if (node.right != null) q.add(node.right);}ans.add(max);}return ans;}
}

563 二叉树的坡度

563. 二叉树的坡度 - 力扣（LeetCode）

给你一个二叉树的根节点 root ，计算并返回 整个树 的坡度。

一个树的 节点的坡度 定义即为，该节点左子树的节点之和和右子树节点之和的 差的绝对值 。如果没有左子树的话，左子树的节点之和为 0 ；没有右子树的话也是一样。空结点的坡度是 0 。

整个树 的坡度就是其所有节点的坡度之和。

示例 1：

输入：root = [1,2,3]
输出：1
解释：
节点 2 的坡度：|0-0| = 0（没有子节点）
节点 3 的坡度：|0-0| = 0（没有子节点）
节点 1 的坡度：|2-3| = 1（左子树就是左子节点，所以和是 2 ；右子树就是右子节点，所以和是 3 ）
坡度总和：0 + 0 + 1 = 1

示例 2：

输入：root = [4,2,9,3,5,null,7]
输出：15
解释：
节点 3 的坡度：|0-0| = 0（没有子节点）
节点 5 的坡度：|0-0| = 0（没有子节点）
节点 7 的坡度：|0-0| = 0（没有子节点）
节点 2 的坡度：|3-5| = 2（左子树就是左子节点，所以和是 3 ；右子树就是右子节点，所以和是 5 ）
节点 9 的坡度：|0-7| = 7（没有左子树，所以和是 0 ；右子树正好是右子节点，所以和是 7 ）
节点 4 的坡度：|(3+5+2)-(9+7)| = |10-16| = 6（左子树值为 3、5 和 2 ，和是 10 ；右子树值为 9 和 7 ，和是 16 ）
坡度总和：0 + 0 + 0 + 2 + 7 + 6 = 15

示例 3：

输入：root = [21,7,14,1,1,2,2,3,3]
输出：9

提示：

树中节点数目的范围在 [0, 104] 内
-1000 <= Node.val <= 1000

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int res  = 0;int dfs(TreeNode* root) {if (!root) return 0;int left = dfs(root->left);int right = dfs(root->right);res += abs(left - right);return left + right + root->val;}int findTilt(TreeNode* root) {if (!root) return 0;dfs(root);return res;}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {private int res = 0;public int findTilt(TreeNode root) {if (root == null) return 0;dfs(root);return res;}public int dfs(TreeNode root) {if (root == null) return 0;int left = dfs(root.left);int right = dfs(root.right);res += Math.abs(left - right);return left + right + root.val;}
}

572 另一棵树的子树

572. 另一棵树的子树 - 力扣（LeetCode）

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

示例 1：

输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true

示例 2：

输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false

提示：

root 树上的节点数量范围是 [1, 2000]
subRoot 树上的节点数量范围是 [1, 1000]
-104 <= root.val <= 104
-104 <= subRoot.val <= 104

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool isSubtree(TreeNode* root, TreeNode* subRoot) {if (!root || !subRoot) {return false;}if (isSameTree(root, subRoot)) {return true;}return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);}bool isSameTree(TreeNode* a, TreeNode* b) {if (!a && !b) {return true;}return a && b && a->val == b->val && (isSameTree(a->left, b->left)) && (isSameTree(a->right, b->right));}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isSubtree(TreeNode root, TreeNode subRoot) {if (root == null || subRoot == null) {return false;}if (isSameTree(root, subRoot)) {return true;}return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);}public boolean isSameTree(TreeNode a, TreeNode b) {if (a == null && b == null) {return true;}return (a != null) && (b != null) && a.val == b.val && (isSameTree(a.left, b.left)) && (isSameTree(a.right, b.right));}
}

96 不同的二叉搜索树

96. 不同的二叉搜索树 - 力扣（LeetCode）

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：

输入：n = 3
输出：5

示例 2：

输入：n = 1
输出：1

提示：

1 <= n <= 19

class Solution {
public:int numTrees(int n) {vector<int> dp(n + 1);dp[0] = 1;// dp[i] 1到i为结点组成的二叉搜索树个数for (int i = 1; i <= n; i++) {for (int j = 1; j <= i; j++) {// j-1 为j为头结点左子树的结点个数 i-j 为为j为头结点右子树的结点个数dp[i] += dp[i - j] * dp[j - 1];}}return dp[n];}
};

class Solution {public int numTrees(int n) {int[] dp = new int[n + 1];dp[0] = 1;for (int i = 1; i <= n; i++) {for (int j = 1; j <= i; j++) {dp[i] += dp[i - j] * dp[j - 1];}}return dp[n]; }
}

95 不同的二叉搜索树Ⅱ

95. 不同的二叉搜索树 II - 力扣（LeetCode）

给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。

示例 1：

输入：n = 3
输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

示例 2：

输入：n = 1
输出：[[1]]

提示：

1 <= n <= 8

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<TreeNode*> createTrees(int start, int end) {if (start > end) {return { nullptr };}vector<TreeNode*> allTrees;for (int i = start; i <= end; i++) {vector<TreeNode*> leftTrees = createTrees(start, i - 1);vector<TreeNode*> rightTrees = createTrees(i + 1, end);for (auto &left : leftTrees) {for (auto &right : rightTrees) {TreeNode* cur = new TreeNode(i);cur->left = left;cur->right = right;allTrees.push_back(cur);}}}return allTrees;}vector<TreeNode*> generateTrees(int n) {if (!n) {return {};}return createTrees(1, n);}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<TreeNode> generateTrees(int n) {if (n == 0) {return new ArrayList<TreeNode>();}return createTrees(1, n);}public List<TreeNode> createTrees(int start, int end) {List<TreeNode> allTrees = new ArrayList<>();if (start > end) {allTrees.add(null);return allTrees;}for (int i = start; i <= end; i++) {List<TreeNode> leftTrees = createTrees(start, i - 1);List<TreeNode> rightTrees = createTrees(i + 1, end);for (var left : leftTrees) {for (var right : rightTrees) {TreeNode cur = new TreeNode(i);cur.left = left;cur.right = right;allTrees.add(cur);}}}return allTrees;}
}

98 验证二叉搜索树

98. 验证二叉搜索树 - 力扣（LeetCode）

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

输入：root = [2,1,3]
输出：true

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

树中节点数目范围在[1, 104] 内
-231 <= Node.val <= 231 - 1

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:long pre = LONG_MIN;bool isValidBST(TreeNode* root) {if (!root) {return true;}if (!isValidBST(root->left) || root->val <= pre) {return false;}pre = root->val;return isValidBST(root->right);}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {private long pre = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if (root == null) {return true;}if (!isValidBST(root.left) || root.val <= pre) {return false;}pre = root.val;return isValidBST(root.right);}
}

99 恢复二叉搜索树

99. 恢复二叉搜索树 - 力扣（LeetCode）

给你二叉搜索树的根节点 root ，该树中的恰好两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。

示例 1：

输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。

示例 2：

输入：root = [3,1,4,null,null,2]
输出：[2,1,4,null,null,3]
解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。

提示：

树上节点的数目在范围 [2, 1000] 内
-231 <= Node.val <= 231 - 1

**进阶：**使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用 O(1) 空间的解决方案吗？

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* pre = new TreeNode(INT_MIN);TreeNode* err1 = NULL;TreeNode* err2 = NULL;void dfs(TreeNode* root) {if (!root) {return;}dfs(root->left);if (pre->val > root->val && err1 == NULL) {err1 = pre;}if (pre->val > root->val && err1 != NULL) {err2 = root;}pre = root;dfs(root->right);}void recoverTree(TreeNode* root) {dfs(root);int temp = err1->val;err1->val = err2->val;err2->val = temp;}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {private TreeNode pre = new TreeNode(Integer.MIN_VALUE);private TreeNode err1 = null;private TreeNode err2 = null;public void recoverTree(TreeNode root) {dfs(root);int temp = err1.val;err1.val = err2.val;err2.val = temp;}public void dfs(TreeNode root) {// 第一种情况 两个错误(两处降序) 交换第一处的第一个数和第二处的第二个数// 第二种情况 一处错误 直接交换即可if (root == null) {return;}dfs(root.left);if (pre.val > root.val && err1 == null) {err1 = pre;}if (pre.val > root.val && err1 != null) {err2 = root;}pre = root;dfs(root.right);}
}

108 将有序数组转换为二叉搜索树

108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：

输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示：

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 按 严格递增 顺序排列

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* build(vector<int>& nums, int left, int right) {if (left > right) return nullptr;int mid = (left + right) >> 1;TreeNode* ans = new TreeNode(nums[mid]);ans->left = build(nums, left, mid - 1);ans->right = build(nums, mid + 1, right);return ans;}TreeNode* sortedArrayToBST(vector<int>& nums) {return build(nums, 0, nums.size() - 1);}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode sortedArrayToBST(int[] nums) {return build(nums, 0, nums.length - 1);}public TreeNode build(int[] nums, int left, int right) {if (left > right) return null;int mid = (left + right) >> 1;TreeNode ans = new TreeNode(nums[mid]);ans.left = build(nums, left, mid - 1);ans.right = build(nums, mid + 1, right);return ans;}
}

109 有序链表转换二叉搜索树

109. 有序链表转换二叉搜索树 - 力扣（LeetCode）

给定一个单链表的头节点 head ，其中的元素 按升序排序 ，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。

示例 1:

输入: head = [-10,-3,0,5,9]
输出: [0,-3,9,-10,null,5]
解释: 一个可能的答案是[0，-3,9，-10,null,5]，它表示所示的高度平衡的二叉搜索树。

示例 2:

输入: head = []
输出: []

提示:

head 中的节点数在[0, 2 * 104] 范围内
-105 <= Node.val <= 105

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:ListNode* node;TreeNode* sortedListToBST(ListNode* head) {node = head;int n = 0;ListNode* cur = head;while (cur) {cur = cur->next;n++;}return build(0, n - 1);}TreeNode* build(int l, int r) {if (l > r) return nullptr;int mid = (l + r) >> 1;TreeNode* left = build(l, mid - 1);TreeNode* ans = new TreeNode(node->val);node = node->next;ans->left = left;ans->right = build(mid + 1, r);return ans;}
};

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {private ListNode head;public TreeNode sortedListToBST(ListNode node) {head = node;int n = 0;ListNode cur = head;while (cur != null) {cur = cur.next;n++;}return build(0, n - 1);}public TreeNode build(int l, int r) {if (l > r) {return null;}int mid = (l + r) >> 1;TreeNode left = build(l, mid - 1);TreeNode ans = new TreeNode(head.val);head = head.next;ans.left = left;ans.right = build(mid + 1, r);return ans;}
}

173 二叉搜索树迭代器

173. 二叉搜索树迭代器 - 力扣（LeetCode）

实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：

BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。
boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。
int next()将指针向右移动，然后返回指针处的数字。

注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。

你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。

示例：

输入
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
输出
[null, 3, 7, true, 9, true, 15, true, 20, false]解释
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next();    // 返回 3
bSTIterator.next();    // 返回 7
bSTIterator.hasNext(); // 返回 True
bSTIterator.next();    // 返回 9
bSTIterator.hasNext(); // 返回 True
bSTIterator.next();    // 返回 15
bSTIterator.hasNext(); // 返回 True
bSTIterator.next();    // 返回 20
bSTIterator.hasNext(); // 返回 False

提示：

树中节点的数目在范围 [1, 105] 内
0 <= Node.val <= 106
最多调用 105 次 hasNext 和 next 操作

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class BSTIterator {
public:stack<TreeNode*> st;BSTIterator(TreeNode* root) {while (root) {st.push(root);root = root->left;}}int next() {TreeNode* cur = st.top();st.pop();int res = cur->val;cur = cur->right;while (cur) {st.push(cur);cur = cur->left;}return res;}bool hasNext() {return !st.empty();}
};/*** Your BSTIterator object will be instantiated and called as such:* BSTIterator* obj = new BSTIterator(root);* int param_1 = obj->next();* bool param_2 = obj->hasNext();*/

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class BSTIterator {private Deque<TreeNode> st = new ArrayDeque<>();public BSTIterator(TreeNode root) {while (root != null) {st.addLast(root);root = root.left;}}public int next() {TreeNode cur = st.pollLast();int res = cur.val;cur = cur.right;while (cur != null) {st.addLast(cur);cur = cur.left;}return res;}public boolean hasNext() {return !st.isEmpty();}
}/*** Your BSTIterator object will be instantiated and called as such:* BSTIterator obj = new BSTIterator(root);* int param_1 = obj.next();* boolean param_2 = obj.hasNext();*/

2476 二叉搜索树最近节点查询

2476. 二叉搜索树最近节点查询 - 力扣（LeetCode）

给你一个 二叉搜索树 的根节点 root ，和一个由正整数组成、长度为 n 的数组 queries 。

请你找出一个长度为 n 的二维答案数组 answer ，其中 answer[i] = [mini, maxi] ：

mini 是树中小于等于 queries[i] 的 最大值 。如果不存在这样的值，则使用 -1 代替。
maxi 是树中大于等于 queries[i] 的 最小值 。如果不存在这样的值，则使用 -1 代替。

返回数组 answer 。

示例 1 ：

输入：root = [6,2,13,1,4,9,15,null,null,null,null,null,null,14], queries = [2,5,16]
输出：[[2,2],[4,6],[15,-1]]
解释：按下面的描述找出并返回查询的答案：
- 树中小于等于 2 的最大值是 2 ，且大于等于 2 的最小值也是 2 。所以第一个查询的答案是 [2,2] 。
- 树中小于等于 5 的最大值是 4 ，且大于等于 5 的最小值是 6 。所以第二个查询的答案是 [4,6] 。
- 树中小于等于 16 的最大值是 15 ，且大于等于 16 的最小值不存在。所以第三个查询的答案是 [15,-1] 。

示例 2 ：

输入：root = [4,null,9], queries = [3]
输出：[[-1,4]]
解释：树中不存在小于等于 3 的最大值，且大于等于 3 的最小值是 4 。所以查询的答案是 [-1,4] 。

提示：

树中节点的数目在范围 [2, 105] 内
1 <= Node.val <= 106
n == queries.length
1 <= n <= 105
1 <= queries[i] <= 106

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {vector<int> a;void dfs(TreeNode* root) {if (!root) {return;}dfs(root->left);a.push_back(root->val);dfs(root->right);}public:vector<vector<int>> closestNodes(TreeNode* root, vector<int>& queries) {dfs(root);int n = a.size();vector<vector<int>> ans;for (auto q : queries) {int j = ranges::lower_bound(a, q) - a.begin();int mx = j == n ? -1 : a[j];if (j == n || a[j] != q) {j--;}int mn = j < 0 ? -1 : a[j];ans.push_back({mn, mx});}return ans;}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) {List<Integer> arr = new ArrayList<>();dfs(root, arr);int n = arr.size();int[] a = new int[n];for (int i = 0; i < n; i++) {a[i] = arr.get(i);}List<List<Integer>> ans = new ArrayList<>(queries.size());for (int q : queries) {int j = lower_bound(a, q);int mx = j == n ? -1 : a[j];if (j == n || a[j] != q) {j--;}int mn = j < 0 ? -1 : a[j];ans.add(List.of(mn, mx));}return ans;}public void dfs(TreeNode root, List<Integer> a) {if (root == null) {return;}dfs(root.left, a);a.add(root.val);dfs(root.right, a);}public int lower_bound(int[] a, int target) {int left = -1, right = a.length;while (left + 1 < right) {int mid = (left + right) >> 1;if (a[mid] < target) {left = mid;} else {right = mid;}}return right;}
}

235 二叉搜索树的最近公共祖先

235. 二叉搜索树的最近公共祖先 - 力扣（LeetCode）

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

所有节点的值都是唯一的。
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) {TreeNode* node = root;while (true) {if (p->val < node->val && q->val < node->val) {node = node->left;} else if (p->val > node->val && q->val > node->val) {node = node->right;} else {break;}}return node;}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {//二叉搜素树有序可以确定p q的位置 无需判断root为空 找到便返回int x = root.val;if (p.val < x && q.val < x) {return lowestCommonAncestor(root.left,p,q);}if (p.val > x && q.val > x) {return lowestCommonAncestor(root.right,p,q);}return root;}
}

938 二叉搜索树的范围和

938. 二叉搜索树的范围和 - 力扣（LeetCode）

给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。

示例 1：

输入：root = [10,5,15,3,7,null,18], low = 7, high = 15
输出：32

示例 2：

输入：root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
输出：23

提示：

树中节点数目在范围 [1, 2 * 104] 内
1 <= Node.val <= 105
1 <= low <= high <= 105
所有 Node.val 互不相同

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int rangeSumBST(TreeNode* root, int low, int high) {if (!root) {return 0;}int x = root->val;int sum = low <= x && x <= high ? x : 0;if (low < x) {sum += rangeSumBST(root->left, low, high);}if (high > x) {sum += rangeSumBST(root->right, low, high);}return sum;}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int rangeSumBST(TreeNode root, int low, int high) {if (root == null) {return 0;}int x = root.val;int sum = low <= x && high >= x ? x : 0;if (x > low) {sum += rangeSumBST(root.left, low, high);}if (x < high) {sum += rangeSumBST(root.right, low, high);}return sum;}
}

230 二叉搜索树中第K小的元素

230. 二叉搜索树中第K小的元素 - 力扣（LeetCode）

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

示例 1：

输入：root = [3,1,4,null,2], k = 1
输出：1

示例 2：

输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3

提示：

树中的节点数为 n 。
1 <= k <= n <= 104
0 <= Node.val <= 104

**进阶：**如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int kthSmallest(TreeNode* root, int k) {stack<TreeNode*> st;TreeNode* cur = root;int ans = 0;while (cur || !st.empty()) {if (cur) {st.push(cur);cur = cur->left;} else {cur = st.top();st.pop();if (--k == 0) {ans = cur->val;}cur = cur->right;}}return ans;}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {private int ans;// 接收答案private int p; // 接收kpublic int kthSmallest(TreeNode root, int k) {p = k;dfs(root);return ans;}private void dfs(TreeNode root) {//中序遍历if (root == null) {return;}dfs(root.left);if (--p == 0) {ans = root.val;// 更新答案}dfs(root.right);}
}

450 删除二叉搜索树中的节点

450. 删除二叉搜索树中的节点 - 力扣（LeetCode）

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点；
如果找到了，删除它。

示例 1:

输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]
解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。

示例 2:

输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的节点

示例 3:

输入: root = [], key = 0
输出: []

提示:

节点数的范围 [0, 104].
-105 <= Node.val <= 105
节点值唯一
root 是合法的二叉搜索树
-105 <= key <= 105

进阶： 要求算法时间复杂度为 O(h)，h 为树的高度。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* deleteNode(TreeNode* root, int key) {if (root == nullptr) return root;if (root->val == key) {if (root->left == nullptr && root->right == nullptr) {delete root;return nullptr;} else if (root->left == nullptr) {auto node = root->right;delete root;return node;} else if (root->right == nullptr) {auto node = root->left;delete root;return node;} else {auto cur = root->right;while (cur->left) {cur = cur->left;}cur->left = root->left;auto tmp = root;root = root->right;delete tmp;return root;}}if (root->val > key) root->left = deleteNode(root->left, key);if (root->val < key) root->right = deleteNode(root->right, key);return root;}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode deleteNode(TreeNode root, int key) {if (root == null) return root;if (root.val == key) {if (root.left == null && root.right == null) {return null;} else if (root.left == null) {return root.right;} else if (root.right == null) {return root.left;} else {TreeNode cur = root.right;while (cur.left != null) {cur = cur.left;}cur.left = root.left;TreeNode tmp = root;root = root.right;return root;}}if (root.val > key) root.left = deleteNode(root.left, key);if (root.val < key) root.right = deleteNode(root.right, key);return root;}
}

501 二叉搜索树中的众数

501. 二叉搜索树中的众数 - 力扣（LeetCode）

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树

示例 1：

输入：root = [1,null,2,2]
输出：[2]

示例 2：

输入：root = [0]
输出：[0]

提示：

树中节点的数目在范围 [1, 104] 内
-105 <= Node.val <= 105

**进阶：**你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int count;int maxcount;TreeNode* pre;vector<int> res;void dfs(TreeNode* cur) {if (cur == NULL) return;dfs(cur->left);if (pre == NULL) {count = 1;} else if (pre->val == cur->val) {count++;} else {count = 1;}pre = cur;if (count == maxcount) {res.push_back(cur->val);}if (count > maxcount) {maxcount = count;res.clear();res.push_back(cur->val);}dfs(cur->right);return;}vector<int> findMode(TreeNode* root) {int count = 0;int maxcount = 0;TreeNode* pre = NULL;res.clear();dfs(root);return res;}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {List<Integer> ans = new ArrayList<>();int cur = 0;int cnt = 0;int maxcnt = 0;public int[] findMode(TreeNode root) {dfs(root);int[] res = new int[ans.size()];for(int i = 0; i < ans.size(); i++) {res[i] = ans.get(i);}return res;}private void dfs(TreeNode root) {if (root == null) {return;}dfs(root.left);if (root.val == cur) {cnt++;} else {cur = root.val;cnt = 1;}if (maxcnt == cnt) {ans.add(root.val);} else if (maxcnt < cnt) {ans.clear();ans.add(root.val);maxcnt = cnt;}dfs(root.right);}
}

530 二叉搜索树的最小绝对差

530. 二叉搜索树的最小绝对差 - 力扣（LeetCode）

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

示例 1：

输入：root = [4,2,6,1,3]
输出：1

示例 2：

输入：root = [1,0,48,null,null,12,49]
输出：1

提示：

树中节点的数目范围是 [2, 104]
0 <= Node.val <= 105

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int ans = INT_MAX;int pre = -1;void dfs(TreeNode* root) {if (!root) return;dfs(root->left);if (pre != -1) {ans = min(ans, root->val - pre);}pre = root->val;dfs(root->right);}int getMinimumDifference(TreeNode* root) {dfs(root);return ans;}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {private int pre = -1; //记录前一个节点的值private int ans = Integer.MAX_VALUE;public int getMinimumDifference(TreeNode root) {dfs(root);return ans;}private void dfs(TreeNode root) {if (root == null) {return;}dfs(root.left);if (pre != -1) {ans = Math.min(ans, root.val - pre);}pre = root.val;dfs(root.right);}
}

538 把二叉搜索树转换为累加树

538. 把二叉搜索树转换为累加树 - 力扣（LeetCode）

给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

节点的左子树仅包含键小于节点键的节点。
节点的右子树仅包含键大于节点键的节点。
左右子树也必须是二叉搜索树。

**注意：**本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同

示例 1：

输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

示例 2：

输入：root = [0,null,1]
输出：[1,null,1]

示例 3：

输入：root = [1,0,2]
输出：[3,3,2]

示例 4：

输入：root = [3,2,4,1]
输出：[7,9,4,10]

提示：

树中的节点数介于 0 和 104 之间。
每个节点的值介于 -104 和 104 之间。
树中的所有值 互不相同 。
给定的树为二叉搜索树。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int s = 0;void dfs(TreeNode* root) {if (!root) return;dfs(root->right);s += root->val;root->val = s;dfs(root->left);}TreeNode* convertBST(TreeNode* root) {dfs(root);return root;}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {private int s = 0;public TreeNode convertBST(TreeNode root) {dfs(root);return root;}private void dfs(TreeNode root) {if (root == null) return;dfs(root.right);s += root.val;root.val = s;dfs(root.left);}
}

222 完全二叉树的节点个数

222. 完全二叉树的节点个数 - 力扣（LeetCode）

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

示例 1：

输入：root = [1,2,3,4,5,6]
输出：6

示例 2：

输入：root = []
输出：0

示例 3：

输入：root = [1]
输出：1

提示：

树中节点的数目范围是[0, 5 * 104]
0 <= Node.val <= 5 * 104
题目数据保证输入的树是 完全二叉树

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int countLevels(TreeNode* root) {int depth = 0;while (root) {root = root->left;depth++;}return depth;}int countNodes(TreeNode* root) {if (!root) return 0;int left = countLevels(root->left);int right = countLevels(root->right);if (left == right) {return countNodes(root->right) + (1 << left);} else {return countNodes(root->left) + (1 << right);}}
};

110 平衡二叉树

110. 平衡二叉树 - 力扣（LeetCode）

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例 3：

输入：root = []
输出：true

提示：

树中的节点数在范围 [0, 5000] 内
-104 <= Node.val <= 104

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int getHeight(TreeNode* root) {if (!root) return 0;int left = getHeight(root->left);if (left == -1) return -1;int right = getHeight(root->right);if (right == -1 || abs(left - right) > 1) return -1;return max(left, right) + 1;}bool isBalanced(TreeNode* root) {return getHeight(root) != -1;}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isBalanced(TreeNode root) {return getHeight(root) != -1;}private int getHeight(TreeNode root) {if (root == null) {return 0;}int left = getHeight(root.left);if (left == -1) { //高度必定为正数，不平衡返回-1return -1;}int right = getHeight(root.right);if (right == -1 || Math.abs(left - right) > 1) {return -1;}return Math.max(left, right) + 1; //二叉树平衡，返回高度}
}

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int countNodes(TreeNode root) {if (root == null) {return 0;}int left = countLevels(root.left);int right = countLevels(root.right);if (left == right) {return countNodes(root.right) + (1 << left);} else {return countNodes(root.left) + (1 << right);}}public int countLevels(TreeNode root) {int level = 0;while (root != null) {root = root.left;level++;}return level;}
}

116 填充每个节点的下一个右侧节点指针

116. 填充每个节点的下一个右侧节点指针 - 力扣（LeetCode）

117. 填充每个节点的下一个右侧节点指针 II - 力扣（LeetCode）

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {int val;Node *left;Node *right;Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

示例 1：

输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。

示例 2:

输入：root = []
输出：[]

提示：

树中节点的数量在 [0, 212 - 1] 范围内
-1000 <= node.val <= 1000

进阶：

你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

/*
// Definition for a Node.
class Node {
public:int val;Node* left;Node* right;Node* next;Node() : val(0), left(NULL), right(NULL), next(NULL) {}Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}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* dummy = new Node();Node* cur = root;while (cur) {dummy->next = nullptr;Node* nxt = dummy;while (cur) {if (cur->left) {nxt->next = cur->left;nxt = cur->left;}if (cur->right) {nxt->next = cur->right;nxt = cur->right;}cur = cur->next;}cur = dummy->next;}delete dummy;return root;}
};

/*
// Definition for a Node.
class Node {public int val;public Node left;public Node right;public Node next;public Node() {}public Node(int _val) {val = _val;}public 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 dummy = new Node();Node cur = root;while (cur != null) {dummy.next = null;Node nxt = dummy; // 下一层的链表while (cur != null) {if (cur.left != null) {nxt.next = cur.left;nxt = cur.left;}if (cur.right != null) {nxt.next = cur.right;nxt = cur.right;}cur = cur.next; // 当前层链表的下一个结点}cur = dummy.next; // 下一层链表的头结点}return root;}
}

226 翻转二叉树

226. 翻转二叉树 - 力扣（LeetCode）

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

示例 2：

输入：root = [2,1,3]
输出：[2,3,1]

示例 3：

输入：root = []
输出：[]

提示：

树中节点数目范围在 [0, 100] 内
-100 <= Node.val <= 100

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* invertTree(TreeNode* root) {if (!root) return nullptr;TreeNode* left = invertTree(root->left);TreeNode* right = invertTree(root->right);root->left = right;root->right = left;return root;}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode invertTree(TreeNode root) {if (root == null) {return null;}TreeNode left = invertTree(root.left);TreeNode right = invertTree(root.right);root.right = left;root.left = right;return root;}
}

617 合并二叉树

617. 合并二叉树 - 力扣（LeetCode）

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

示例 1：

输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]

示例 2：

输入：root1 = [1], root2 = [1,2]
输出：[2,2]

提示：

两棵树中的节点数目在范围 [0, 2000] 内
-104 <= Node.val <= 104

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {if (!root1) return root2;if (!root2) return root1;return new TreeNode(root1->val + root2->val, mergeTrees(root1->left, root2->left), mergeTrees(root1->right, root2->right));}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if (root1 == null) return root2;if (root2 == null) return root1;return new TreeNode(root1.val + root2.val, mergeTrees(root1.left, root2.left), mergeTrees(root1.right, root2.right));}
}

404 左子树之和

404. 左叶子之和 - 力扣（LeetCode）

给定二叉树的根节点 root ，返回所有左叶子之和。

示例 1：

输入: root = [3,9,20,null,null,15,7] 
输出: 24 
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

示例 2:

输入: root = [1]
输出: 0

提示:

节点数在 [1, 1000] 范围内
-1000 <= Node.val <= 1000

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool isLeaf(TreeNode* root) {return !root->left && !root->right;}int dfs(TreeNode* root) {int ans = 0;if (root->left) {ans += isLeaf(root->left) ? root->left->val : dfs(root->left);}if (root->right && !isLeaf(root->right)) {ans += dfs(root->right);}return ans;}int sumOfLeftLeaves(TreeNode* root) {return root ? dfs(root) : 0;}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int sumOfLeftLeaves(TreeNode root) {return root == null ? 0 : dfs(root);}public boolean isLeaf(TreeNode root) {return root.left == null && root.right == null;}public int dfs(TreeNode root) {int ans = 0;if (root.left != null) {ans += isLeaf(root.left) ? root.left.val : dfs(root.left);}if (root.right != null && !isLeaf(root.right)) {ans += dfs(root.right);}return ans;}
}

1261 在受污染的二叉树中查找元素

1261. 在受污染的二叉树中查找元素 - 力扣（LeetCode）

给出一个满足下述规则的二叉树：

root.val == 0
如果 treeNode.val == x 且 treeNode.left != null，那么 treeNode.left.val == 2 * x + 1
如果 treeNode.val == x 且 treeNode.right != null，那么 treeNode.right.val == 2 * x + 2

现在这个二叉树受到「污染」，所有的 treeNode.val 都变成了 -1。

请你先还原二叉树，然后实现 FindElements 类：

FindElements(TreeNode* root) 用受污染的二叉树初始化对象，你需要先把它还原。
bool find(int target) 判断目标值 target 是否存在于还原后的二叉树中并返回结果。

示例 1：

输入：
["FindElements","find","find"]
[[[-1,null,-1]],[1],[2]]
输出：
[null,false,true]
解释：
FindElements findElements = new FindElements([-1,null,-1]); 
findElements.find(1); // return False 
findElements.find(2); // return True

示例 2：

输入：
["FindElements","find","find","find"]
[[[-1,-1,-1,-1,-1]],[1],[3],[5]]
输出：
[null,true,true,false]
解释：
FindElements findElements = new FindElements([-1,-1,-1,-1,-1]);
findElements.find(1); // return True
findElements.find(3); // return True
findElements.find(5); // return False

示例 3：

输入：
["FindElements","find","find","find","find"]
[[[-1,null,-1,-1,null,-1]],[2],[3],[4],[5]]
输出：
[null,true,false,false,true]
解释：
FindElements findElements = new FindElements([-1,null,-1,-1,null,-1]);
findElements.find(2); // return True
findElements.find(3); // return False
findElements.find(4); // return False
findElements.find(5); // return True

提示：

TreeNode.val == -1
二叉树的高度不超过 20
节点的总数在 [1, 10^4] 之间
调用 find() 的总次数在 [1, 10^4] 之间
0 <= target <= 10^6

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class FindElements {unordered_set<int> s;void dfs(TreeNode* root, int val) {if (!root) {return;}s.insert(val);dfs(root->left, val * 2 + 1);dfs(root->right, val * 2 + 2);}public:FindElements(TreeNode* root) {dfs(root, 0);}bool find(int target) {return s.contains(target);}
};/*** Your FindElements object will be instantiated and called as such:* FindElements* obj = new FindElements(root);* bool param_1 = obj->find(target);*/

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class FindElements {private final Set<Integer> s = new HashSet<>();public FindElements(TreeNode root) {dfs(root, 0);}public boolean find(int target) {return s.contains(target);}public void dfs(TreeNode root, int val) {if (root == null) {return;}s.add(val);dfs(root.left, val * 2 + 1);dfs(root.right, val * 2 + 2);}
}/*** Your FindElements object will be instantiated and called as such:* FindElements obj = new FindElements(root);* boolean param_1 = obj.find(target);*/

559 N叉树的最大深度

559. N 叉树的最大深度 - 力扣（LeetCode）

给定一个 N 叉树，找到其最大深度。

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。

示例 1：

输入：root = [1,null,3,2,4,null,5,6]
输出：3

示例 2：

输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：5

提示：

树的深度不会超过 1000 。
树的节点数目位于 [0, 104] 之间。

/*
// Definition for a Node.
class Node {
public:int val;vector<Node*> children;Node() {}Node(int _val) {val = _val;}Node(int _val, vector<Node*> _children) {val = _val;children = _children;}
};
*/class Solution {
public:int maxDepth(Node* root) {if (!root) return 0;int ans = 0;queue<Node*> d;d.push(root);while (!d.empty()) {int size = d.size();while (size-- > 0) {Node* n = d.front();d.pop();for (Node* node : n->children) {d.push(node);}}ans++;}return ans;}
};

/*
// Definition for a Node.
class Node {public int val;public List<Node> children;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, List<Node> _children) {val = _val;children = _children;}
};
*/class Solution {public int maxDepth(Node root) {if (root == null) {return 0;}int res = 0;for (Node n : root.children) {res = Math.max(res, maxDepth(n));}return res + 1;}
}

这篇关于【二叉树】LC习题看这一篇就够了！（持续更新...）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

【二叉树】LC习题看这一篇就够了！（持续更新...）

二叉树的遍历

递归

前序

中序

后序

迭代

前序

中序

后序

606 根据二叉树创建字符串

102 二叉树的层序遍历

107 二叉树的层序遍历Ⅱ

103 二叉树的锯齿形层序遍历

623 在二叉树中增加一行

987 二叉树的垂序遍历

236 二叉树的最近公共祖先

993 二叉树的堂兄弟节点

2641 二叉树的堂兄弟节点Ⅱ

105 从前序与中序遍历序列构造二叉树

106 从中序与后序遍历序列构造二叉树

889 根据前序和后序遍历构造二叉树

331 验证二叉树的前序序列化

2583 二叉树中的第K大层和

257 二叉树的所有路径

543 二叉树的直径

112 路径总和

113 路径总和Ⅱ

437 路径总和Ⅲ

114 二叉树展开为链表

124 二叉树中的最大路径和

129 求根节点到叶节点数字之和

199 二叉树的右视图

508 出现次数最多的子树元素和

513 找树左下角的值

515 在每个树行中找最大值

563 二叉树的坡度

572 另一棵树的子树

96 不同的二叉搜索树

95 不同的二叉搜索树Ⅱ

98 验证二叉搜索树

99 恢复二叉搜索树

108 将有序数组转换为二叉搜索树

109 有序链表转换二叉搜索树

173 二叉搜索树迭代器

2476 二叉搜索树最近节点查询

235 二叉搜索树的最近公共祖先

938 二叉搜索树的范围和

230 二叉搜索树中第K小的元素

450 删除二叉搜索树中的节点

501 二叉搜索树中的众数

530 二叉搜索树的最小绝对差

538 把二叉搜索树转换为累加树

222 完全二叉树的节点个数

110 平衡二叉树

116 填充每个节点的下一个右侧节点指针

226 翻转二叉树

617 合并二叉树

404 左子树之和

1261 在受污染的二叉树中查找元素

559 N叉树的最大深度

相关文章