A summary of binary tree related problems from LeetCode with solutions in C++.
Problems:
144. Binary Tree Preorder Traversal
94. Binary Tree Inorder Traversal
145. Binary Tree Postorder Traversal
102. Binary Tree Level Order Traversal
107. Binary Tree Level Order Traversal II
199. Binary Tree Right Side View
637. Average of Levels in Binary Tree
429. N-ary Tree Level Order Traversal
515. Find Largest Value in Each Tree Row
116. Populating Next Right Pointers in Each Node
117. Populating Next Right Pointers in Each Node II
104. Maximum Depth of Binary Tree
111. Minimum Depth of Binary Tree
226. Invert Binary Tree
101. Symmetric Tree
559. Maximum Depth of N-ary Tree
222. Count Complete Tree Nodes
110. Balanced Binary Tree
257. Binary Tree Paths
404. Sum of Left Leaves
513. Find Bottom Left Tree Value
112. Path Sum
113. Path Sum II
106. Construct Binary Tree from Inorder and Postorder Traversal
105. Construct Binary Tree from Preorder and Inorder Traversal
654. Maximum Binary Tree
617. Merge Two Binary Trees
700. Search in a Binary Search Tree
98. Validate Binary Search Tree
530. Minimum Absolute Difference in BST
501. Find Mode in Binary Search Tree
236. Lowest Common Ancestor of a Binary Tree
235. Lowest Common Ancestor of a Binary Search Tree
701. Insert into a Binary Search Tree
450. Delete Node in a BST
669. Trim a Binary Search Tree
108. Convert Sorted Array to Binary Search Tree
538. Convert BST to Greater Tree
1. 144. Binary Tree Preorder Traversal
Problem: Given the root of a binary tree, return the preorder traversal of its nodes’ values.
/**
* 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) {}
* };
*/
// Recursive Method
class Solution {
public:
void traversal(TreeNode* cur, vector<int>& vec) {
if (cur == nullptr) { return; }
vec.push_back(cur->val); // 中
traversal(cur->left, vec); // 左
traversal(cur->right, vec); // 右
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
traversal(root, result);
return result;
}
};
// Iterative Method
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
if (root == nullptr) { return result; }
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top(); // 中
st.pop();
result.push_back(node->val);
if (node->right) { st.push(node->right); } // 右（空节点不入栈）
if (node->left) { st.push(node->left); } // 左（空节点不入栈）
}
return result;
}
};
// Iterative Method
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
if (root != nullptr) { st.push(root); }
while (!st.empty()) {
TreeNode* node = st.top();
if (node != nullptr) {
st.pop();
if (node->right) { st.push(node->right); } // 右
if (node->left) { st.push(node->left); } // 左
st.push(node); // 中
st.push(nullptr);
} else {
st.pop();
node = st.top();
st.pop();
result.push_back(node->val);
}
}
return result;
}
};
2. 94. Binary Tree Inorder Traversal
Problem: Given the root of a binary tree, return the inorder traversal of its nodes’ values.
/**
* 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) {}
* };
*/
// Recursive Method
class Solution {
public:
void traversal(TreeNode* cur, vector<int>& vec) {
if (cur == NULL) { return; }
traversal(cur->left, vec); // 左
vec.push_back(cur->val); // 中
traversal(cur->right, vec); // 右
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
traversal(root, result);
return result;
}
};
// Iterative Method
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
TreeNode* cur = root;
while (cur != nullptr || !st.empty()) {
// 指针来访问节点, 访问到最底层
if (cur != nullptr) {
st.push(cur); // 将访问的节点放进栈
cur = cur->left; // 左
} else {
cur = st.top(); // 从栈里弹出的数据, 就是放进result数组里的数据
st.pop();
result.push_back(cur->val); // 中
cur = cur->right; // 右
}
}
return result;
}
};
// Iterative Method
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
if (root != nullptr) { st.push(root); }
while (!st.empty()) {
TreeNode* node = st.top();
if (node != nullptr) {
// 将该节点弹出, 避免重复操作, 下面再将右中左节点添加到栈中
st.pop();
// 添加右节点(空节点不入栈)
if (node->right) { st.push(node->right); }
// 添加中节点
st.push(node);
// 中节点访问过, 但是还没有处理, 加入空节点做为标记
st.push(nullptr);
// 添加左节点(空节点不入栈)
if (node->left) { st.push(node->left); }
} else { // 只有遇到空节点的时候, 才将下一个节点放进结果集
// 将空节点弹出
st.pop();
// 重新取出栈中元素
node = st.top();
st.pop();
// 加入到结果集
result.push_back(node->val);
}
}
return result;
}
};
3. 145. Binary Tree Postorder Traversal
Problem: Given the root of a binary tree, return the postorder traversal of its nodes’ values.
/**
* 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) {}
* };
*/
// Recursive Method
class Solution {
public:
void traveral(TreeNode *cur, vector<int>& vec) {
if (cur == nullptr) { return; }
traveral(cur->left, vec); // 左
traveral(cur->right, vec); // 右
vec.push_back(cur->val); // 中
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
traveral(root, result);
return result;
}
};
// Iterative Method
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
if (root == nullptr) { return result; }
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
st.pop();
result.push_back(node->val);
if (node->left) st.push(node->left); // 这更改一下入栈顺序 (空节点不入栈)
if (node->right) st.push(node->right); // 空节点不入栈
}
// 中右左
reverse(result.begin(), result.end()); // 将结果反转之后就是左右中
return result;
}
};
// Iterative Method
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
if (root != nullptr) { st.push(root); }
while (!st.empty()) {
TreeNode* node = st.top();
if (node != nullptr) {
st.pop();
st.push(node); // 中
st.push(nullptr);
if (node->right) { st.push(node->right); } // 右
if (node->left) { st.push(node->left); } // 左
} else {
st.pop();
node = st.top();
st.pop();
result.push_back(node->val);
}
}
return result;
}
};
4. 102. Binary Tree Level Order Traversal
Problem: Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).
Case 1: Input: root = [3,9,20,null,null,15,7], Output: [[3],[9,20],[15,7]]
Case 2: Input: root = [1], Output: [[1]]
Case 3: Input: root = [], Output: []
使用队列实现二叉树广度优先遍历 (Credit to Carl)
/**
* 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) {
// result 2D vector
vector<vector<int>> result;
// layer traversal
queue<TreeNode*> que;
if (root != nullptr) { que.push(root); }
while (!que.empty()) {
int size = que.size();
// vec for storing elements in each layer
vector<int> vec;
// 这里使用固定大小size, 因为que.size()是不断变化的
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
vec.push_back(node->val);
if (node->left) { que.push(node->left); }
if (node->right) { que.push(node->right); }
}
// store elements of each layer to result
result.push_back(vec);
}
return result;
}
};
// 递归法
class Solution {
public:
void order(TreeNode* cur, vector<vector<int>>& result, int depth) {
if (cur == nullptr) { return; }
if (result.size() == depth) { result.push_back(vector<int>()); }
result[depth].push_back(cur->val);
order(cur->left, result, depth + 1);
order(cur->right, result, depth + 1);
}
vector<vector<int>> levelOrder(TreeNode* root) {
// result 2D vector
vector<vector<int>> result;
int depth = 0;
order(root, result, depth);
return result;
}
};
5. 107. Binary Tree Level Order Traversal II
Problem: Given the root of a binary tree, return the bottom-up level order traversal of its nodes’ values. (i.e., from left to right, level by level from leaf to root).
Case 1: Input: root = [3,9,20,null,null,15,7], Output: [[15,7],[9,20],[3]]
Case 2: Input: root = [1], Output: [[1]]
Case 3: Input: root = [], Output: []
/**
* 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>> result;
queue<TreeNode*> que;
if (root != nullptr) { que.push(root); }
while (!que.empty()) {
int size = que.size();
// vec for storing elements in each layer
vector<int> vec;
// 这里使用固定大小size, 因为que.size()是不断变化的
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
vec.push_back(node->val);
if (node->left) { que.push(node->left); }
if (node->right) { que.push(node->right); }
}
result.push_back(vec);
}
// 在这里反转一下数组即可
reverse(result.begin(), result.end());
return result;
}
};
6. 199. Binary Tree Right Side View
Problem: Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
Case 1: Input: root = [1,2,3,null,5,null,4], Output: [1,3,4]
Case 2: Input: root = [1,null,3], Output: [1,3]
Case 3: Input: root = [], Output: []
/**
* 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) {}
* };
*/
// 层序遍历的时候, 判断是否遍历到单层的最后面的元素
// 如果是, 就放进result数组中, 随后返回result
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> result;
queue<TreeNode*> que;
if (root != nullptr) { que.push(root); }
while (!que.empty()) {
int size = que.size();
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
// 将每一层的最后元素放入result数组中
if (i == (size - 1)) { result.push_back(node->val); }
if (node->left) { que.push(node->left); }
if (node->right) { que.push(node->right); }
}
}
return result;
}
};
7. 637. Average of Levels in Binary Tree
Problem: Given the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10-5 of the actual answer will be accepted.
Case 1: Input: root = [3,9,20,null,null,15,7], Output: [3.00000,14.50000,11.00000]
Case 2: Input: root = [3,9,20,15,7], Output: [3.00000,14.50000,11.00000]
/**
* 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<double> averageOfLevels(TreeNode* root) {
vector<double> result;
queue<TreeNode*> que;
if (root != nullptr) { que.push(root); }
while (!que.empty()) {
int size = que.size();
// 统计每一层的和
double sum = 0;
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
sum += node->val;
if (node->left) { que.push(node->left); }
if (node->right) { que.push(node->right); }
}
// 将每层均值放进result
result.push_back(sum/size);
}
return result;
}
};
8. 429. N-ary Tree Level Order Traversal
Problem: Given an n-ary tree, return the level order traversal of its nodes’ values. Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value.
Case 1: Input: root = [1,null,3,2,4,null,5,6], Output: [[1],[3,2,4],[5,6]]
Case 2: Input: 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], Output: [[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]
/*
// 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;
}
};
*/
// 给定一个 N 叉树, 返回其节点值的层序遍历 (即从左到右, 逐层遍历)
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
vector<vector<int>> result;
queue<Node*> que;
if (root != nullptr) { que.push(root); }
while (!que.empty()) {
int size = que.size();
vector<int> vec;
for (int i = 0; i < size; i++) {
Node* node = que.front();
que.pop();
vec.push_back(node->val);
// 将节点孩子加入队列
for (int i = 0; i < node->children.size(); i++) {
if (node->children[i]) { que.push(node->children[i]); }
}
}
result.push_back(vec);
}
return result;
}
};
9. 515. Find Largest Value in Each Tree Row
Problem: Given the root of a binary tree, return an array of the largest value in each row of the tree (0-indexed).
Case 1: Input: root = [1,3,2,5,3,null,9], Output: [1,3,9]
Case 2: Input: root = [1,2,3], Output: [1,3]
/**
* 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) {
vector<int> result;
queue<TreeNode*> que;
if (root != nullptr) { que.push(root); }
while (!que.empty()) {
int size = que.size();
// 取每一层的最大值
// INT_MIN = -2147483648
int maxValue = INT_MIN;
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
// Update max value in each layer
maxValue = node->val > maxValue ? node->val : maxValue;
if (node->left) { que.push(node->left); }
if (node->right) { que.push(node->right); }
}
// 把最大值放进result
result.push_back(maxValue);
}
return result;
}
};
10. 116. Populating Next Right Pointers in Each Node
Problem: You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all next pointers are set to NULL.
Case 1: Input: root = [1,2,3,4,5,6,7], Output: [1,#,2,3,#,4,5,6,7,#]
Case 2: Input: root = [], Output: []
/*
// 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) {
queue<Node*> que;
if (root != nullptr) { que.push(root); }
while (!que.empty()) {
int size = que.size();
Node* nodePre;
Node* node;
// Traverse elements in each layer
for (int i = 0; i < size; i++) {
if (i == 0) {
// 取出一层的头结点
nodePre = que.front();
que.pop();
node = nodePre;
} else {
node = que.front();
que.pop();
// 本层前一个节点next指向本节点
nodePre->next = node;
nodePre = nodePre->next;
}
if (node->left) { que.push(node->left); }
if (node->right) { que.push(node->right); }
}
// 本层最后一个节点指向NULL
nodePre->next = nullptr;
}
return root;
}
};
11. 117. Populating Next Right Pointers in Each Node II
Problem: Given a binary tree
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all next pointers are set to NULL.
Case 1: Input: root = [1,2,3,4,5,null,7], Output: [1,#,2,3,#,4,5,7,#]
Case 2: Input: root = [], Output: []
/*
// 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) {
queue<Node*> que;
if (root != nullptr) { que.push(root); }
while (!que.empty()) {
int size = que.size();
Node* nodePre;
Node* node;
// Traverse elements in each layer
for (int i = 0; i < size; i++) {
if (i == 0) {
// 取出一层的头结点
nodePre = que.front();
que.pop();
node = nodePre;
} else {
node = que.front();
que.pop();
// 本层前一个节点next指向本节点
nodePre->next = node;
nodePre = nodePre->next;
}
if (node->left) { que.push(node->left); }
if (node->right) { que.push(node->right); }
}
// 本层最后一个节点指向NULL
nodePre->next = nullptr;
}
return root;
}
};
12. 104. Maximum Depth of Binary Tree
Problem: Given the root of a binary tree, return its maximum depth. A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Case 1: Input: root = [3,9,20,null,null,15,7], Output: 3
Case 2: Input: root = [1,null,2], Output: 2
/**
* 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 maxDepth(TreeNode* root) {
if (root == nullptr) { return 0; }
int depth = 0;
queue<TreeNode*> que;
que.push(root);
while(!que.empty()) {
int size = que.size();
// 记录深度
depth++;
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
if (node->left) { que.push(node->left); }
if (node->right) { que.push(node->right); }
}
}
return depth;
}
};
// 求高度: 后序遍历
class Solution {
public:
int getHeight(TreeNode* node) {
if (node == nullptr) { return 0; }
int leftHeight = getHeight(node->left); // 左
int rightHeight = getHeight(node->right); // 右
int height = 1 + max(leftHeight, rightHeight); // 中
return height;
}
int maxDepth(TreeNode* root) {
return getHeight(root);
}
};
// 求高度: 后序遍历
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == nullptr) { return 0; }
return ( 1 + max(maxDepth(root->left), maxDepth(root->right)) );
}
};
13. 111. Minimum Depth of Binary Tree
Problem: Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. Note: A leaf is a node with no children.
Case 1: Input: root = [3,9,20,null,null,15,7], Output: 2
Case 2: Input: root = [2,null,3,null,4,null,5,null,6], Output: 5
/**
* 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) {}
* };
*/
// 最小深度是从根节点到最近叶子节点的最短路径上的节点数量
// 只有当左右孩子都为空的时候, 才说明遍历的最低点了
// 如果其中一个孩子为空则不是最低点
// Iterative Method - Preorder Traversal
class Solution {
public:
int minDepth(TreeNode* root) {
if (root == nullptr) { return 0; }
int depth = 0;
queue<TreeNode*> que;
que.push(root);
while(!que.empty()) {
int size = que.size();
// 记录最小深度
depth++;
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
if (node->left) { que.push(node->left); }
if (node->right) { que.push(node->right); }
// 当左右孩子都为空的时候, 说明是最低点的一层了, 退出
if (!node->left && !node->right) {
return depth;
}
}
}
return depth;
}
};
// Recursive Method - Preorder Traversal
class Solution {
private:
int result;
void getDepth(TreeNode* node, int depth) {
if (node->left == nullptr && node->right == nullptr) {
result = min(depth, result);
return;
}
// 中, 只不过中没有处理的逻辑
if (node->left) { // 左
getDepth(node->left, depth + 1);
}
if (node->right) { // 右
getDepth(node->right, depth + 1);
}
return;
}
public:
int minDepth(TreeNode* root) {
if (root == nullptr) { return 0; }
result = INT_MAX;
getDepth(root, 1);
return result;
}
};
// Recursive Method - Postorder Traversal
class Solution {
public:
int getHeight(TreeNode* node) {
if (node == nullptr) { return 0; }
int leftHeight = getHeight(node->left); // 左
int rightHeight = getHeight(node->right); // 右
// 中
// 当一个左子树为空, 右不为空, 这时并不是最低点
if (node->left == nullptr && node->right != nullptr) {
return 1 + rightHeight;
}
// 当一个右子树为空, 左不为空, 这时并不是最低点
if (node->left != nullptr && node->right == nullptr) {
return 1 + leftHeight;
}
// 最小高度
int result = 1 + min(leftHeight, rightHeight);
return result;
}
int minDepth(TreeNode* root) {
return getHeight(root);
}
};
class Solution {
public:
int minDepth(TreeNode* root) {
if (root == nullptr) { return 0; }
// 当一个左子树为空, 右不为空, 这时并不是最低点
if (root->left == nullptr && root->right != nullptr) {
return 1 + minDepth(root->right);
}
// 当一个右子树为空, 左不为空, 这时并不是最低点
if (root->left != nullptr && root->right == nullptr) {
return 1 + minDepth(root->left);
}
return 1 + min(minDepth(root->left), minDepth(root->right));
}
};
Problem: Given the root of a binary tree, invert the tree, and return its root.
Case 1: Input: root = [4,2,7,1,3,6,9], Output: [4,7,2,9,6,3,1]
Case 2: Input: root = [2,1,3], Output: [2,3,1]
Case 3: Input: root = [], Output: []
/**
* 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) {}
* };
*/
// 只要把每一个节点的左右孩子翻转一下, 就可以达到整体翻转的效果
// 这道题目使用前序遍历和后序遍历都可以, 中序遍历不方便, 因为中序遍历会把某些节点的左右孩子翻转了两次
// Recursive Method (递归法) - Preorder Traversal
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == nullptr) { return root; }
swap(root->left, root->right); // 中
invertTree(root->left); // 左
invertTree(root->right); // 右
return root;
}
};
// Iterative Method (迭代法) - Preorder Traversal
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == nullptr) { return root; }
stack<TreeNode*> st;
st.push(root);
while(!st.empty()) {
TreeNode* node = st.top(); // 中
st.pop();
swap(node->left, node->right);
if(node->right) { st.push(node->right); } // 右
if(node->left) { st.push(node->left); } // 左
}
return root;
}
};
// Iterative Method (统一迭代法) - Preorder Traversal
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
stack<TreeNode*> st;
if (root != nullptr) st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
if (node != nullptr) {
st.pop();
if (node->right) st.push(node->right); // 右
if (node->left) st.push(node->left); // 左
st.push(node); // 中
st.push(nullptr);
} else {
st.pop();
node = st.top();
st.pop();
swap(node->left, node->right); // 节点处理逻辑
}
}
return root;
}
};
// Layer Traversal Method
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
queue<TreeNode*> que;
if (root != nullptr) { que.push(root); }
while (!que.empty()) {
int size = que.size();
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
swap(node->left, node->right);
if (node->left) { que.push(node->left); }
if (node->right){ que.push(node->right); }
}
}
return root;
}
};
Problem: Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
Case 1: Input: root = [1,2,2,3,4,4,3], Output: true
Case 2: Input: root = [1,2,2,null,3,null,3], Output: false
/**
* 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 compare(TreeNode* left, TreeNode* right) {
if (left == nullptr && right != nullptr) { return false; }
else if (left != nullptr && right == nullptr) { return false; }
else if (left == nullptr && right == nullptr) { return true; }
else if (left->val != right->val) { return false; }
else {
// return compare(left->left, right->right) && compare(left->right, right->left);
bool outside = compare(left->left, right->right); // 左子树：左, 右子树：右
bool inside = compare(left->right, right->left); // 左子树：右, 右子树：左
bool isSame = outside && inside; // 左子树：中, 右子树: 中 (逻辑处理)
return isSame;
}
}
bool isSymmetric(TreeNode* root) {
if (root == nullptr) { return true; }
return compare(root->left, root->right);
}
};
// Use Queue
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (root == nullptr) { return true; }
queue<TreeNode*> que;
que.push(root->left); // 将左子树头结点加入队列
que.push(root->right); // 将右子树头结点加入队列
while (!que.empty()) { // 接下来就要判断这两个树是否相互翻转
TreeNode* leftNode = que.front();
que.pop();
TreeNode* rightNode = que.front();
que.pop();
// 左节点为空, 右节点为空, 此时说明是对称的
if (!leftNode && !rightNode) {
continue;
}
// 左右一个节点不为空, 或者都不为空但数值不相同, 返回false
if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
return false;
}
que.push(leftNode->left); // 加入左节点左孩子
que.push(rightNode->right); // 加入右节点右孩子
que.push(leftNode->right); // 加入左节点右孩子
que.push(rightNode->left); // 加入右节点左孩子
}
return true;
}
};
// Stack Method
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (root == nullptr) { return true; }
stack<TreeNode*> st;
st.push(root->left);
st.push(root->right);
while (!st.empty()) {
TreeNode* leftNode = st.top();
st.pop();
TreeNode* rightNode = st.top();
st.pop();
if (!leftNode && !rightNode) {
continue;
}
if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
return false;
}
st.push(leftNode->left); // 加入左节点左孩子
st.push(rightNode->right); // 加入右节点右孩子
st.push(leftNode->right); // 加入左节点右孩子
st.push(rightNode->left); // 加入右节点左孩子
}
return true;
}
};
Related problems
100. Same Tree
572. Subtree of Another Tree
16. 559. Maximum Depth of N-ary Tree
Problem: Given a n-ary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).
Case 1: Input: root = [1,null,3,2,4,null,5,6], Output: 3
Case 2: Input: 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], Output: 5
/*
// 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;
}
};
*/
// Recursive Method
class Solution {
public:
int maxDepth(Node* root) {
if (root == 0) { return 0; }
int depth = 0;
for (int i = 0; i < root->children.size(); i++) {
depth = max(depth, maxDepth(root->children[i]));
}
return depth + 1;
}
};
// Iterative Method
class Solution {
public:
int maxDepth(Node* root) {
queue<Node*> que;
if (root != nullptr) { que.push(root); }
int depth = 0;
while (!que.empty()) {
int size = que.size();
depth++; // 记录深度
for (int i = 0; i < size; i++) {
Node* node = que.front();
que.pop();
for (int j = 0; j < node->children.size(); j++) {
if (node->children[j]) que.push(node->children[j]);
}
}
}
return depth;
}
};
17. 222. Count Complete Tree Nodes
Problem: Given the root of a complete binary tree, return the number of the nodes in the tree. According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h. Design an algorithm that runs in less than O(n) time complexity.
Case 1: Input: root = [1,2,3,4,5,6], Output: 6
Case 2: Input: root = [], Output: 0
Case 3: Input: root = [1], Output: 0
(1) 可以直接用2^树深度-1来计算, 注意这里根节点深度为1 (Credit to Carl)
(2) 分别递归左孩子和右孩子, 递归到某一深度一定会有左孩子或者右孩子为满二叉树, 然后依然可以按照情况1来计算 (Credit to Carl)
可以看出如果整个树不是满二叉树, 就递归其左右孩子, 直到遇到满二叉树为止, 用公式计算这个子树(满二叉树)的节点数量。在完全二叉树中, 如果递归向左遍历的深度等于递归向右遍历的深度, 那说明就是满二叉树
在完全二叉树中, 如果递归向左遍历的深度不等于递归向右遍历的深度, 则说明不是满二叉树
/**
* 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) {}
* };
*/
// Postorder Traversal
class Solution {
private:
int getNodesNum(TreeNode* cur) {
if (cur == nullptr) { return 0; }
int leftNum = getNodesNum(cur->left); // 左
int rightNum = getNodesNum(cur->right); // 右
int treeNum = leftNum + rightNum + 1; // 中
return treeNum;
}
public:
int countNodes(TreeNode* root) {
return getNodesNum(root);
}
};
class Solution {
public:
// Time complexity: O(n)
// Space complexity: O(logn)
int countNodes(TreeNode* root) {
if (root == nullptr) { return 0; }
return 1 + countNodes(root->left) + countNodes(root->right);
}
};
// Iterative Method
class Solution {
public:
// Time complexity: O(n)
// Space complexity: O(n)
int countNodes(TreeNode* root) {
queue<TreeNode*> que;
if (root != nullptr) { que.push(root); }
int result = 0;
while (!que.empty()) {
int size = que.size();
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
result++; // 记录节点数量
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
}
return result;
}
};
// Make use of feature of a Complete Binary Tree
class Solution {
public:
// Time complexity: O(logn x logn)
// Space complexity: O(logn)
int countNodes(TreeNode* root) {
if (root == nullptr) { return 0; }
TreeNode* left = root->left;
TreeNode* right = root->right;
// 初始为0是为了下面求指数方便
int leftDepth = 0;
int rightDepth = 0;
// 求左子树深度
while (left) {
left = left->left;
leftDepth++;
}
// 求右子树深度
while (right) {
right = right->right;
rightDepth++;
}
if (leftDepth == rightDepth) {
// 注意(2<<1) 相当于2^2，所以leftDepth初始为0
return (2 << leftDepth) - 1;
}
return countNodes(root->left) + countNodes(root->right) + 1;
}
};
Problem: Given a binary tree, determine if it is height-balanced.
Case 1: Input: root = [3,9,20,null,null,15,7], Output: true
Case 2: root = [1,2,2,3,3,null,null,4,4], Output: false
Case 3: Input: root = [], Output: true
/**
* 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) {}
* };
*/
// 高度(从下到上): 后序遍历
// 深度(从上到下): 前序遍历
// Recursive Method: Postorder Traveral
class Solution {
public:
// 返回以该节点为根节点的二叉树的高度，如果不是平衡二叉树了则返回-1
int getHeight(TreeNode* node) {
// 空节点高度为0
if (node == nullptr) { return 0; }
int leftHeight = getHeight(node->left); // 左
if (leftHeight == -1) { return -1; }
int rightHeight = getHeight(node->right); // 右
if (rightHeight == -1) { return -1; }
return abs(leftHeight - rightHeight) > 1 ? -1 : 1 + max(leftHeight, rightHeight);
}
bool isBalanced(TreeNode* root) {
return getHeight(root) == -1 ? false : true;
}
};
Problem: Given the root of a binary tree, return all root-to-leaf paths in any order. A leaf is a node with no children.
Case 1: Input: root = [1,2,3,null,5], Output: [“1->2->5″,”1->3”]
Case 2: Input: root = [1], Output: [“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) {}
* };
*/
// 给定一个二叉树, 返回所有从根节点到叶子节点的路径
// Recursive Method - Preorder Traversal
class Solution {
private:
void traversal(TreeNode* cur, vector<int>& path, vector<string>& result) {
// 中, 中为什么写在这里, 因为最后一个节点也要加入到path中
path.push_back(cur->val);
// 遍历到叶子节点
if (cur->left == nullptr && cur->right == nullptr) {
string sPath;
for (int i = 0; i < path.size() - 1; i++) {
sPath += to_string(path[i]);
sPath += "->";
}
sPath += to_string(path[path.size() - 1]);
result.push_back(sPath);
return;
}
if (cur->left) { // 左
traversal(cur->left, path, result);
path.pop_back(); // 回溯
}
if (cur->right) { // 右
traversal(cur->right, path, result);
path.pop_back(); // 回溯
}
}
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> result;
vector<int> path;
if (root == nullptr) { return result; }
traversal(root, path, result);
return result;
}
};
// 精简版
class Solution {
private:
void traversal(TreeNode* cur, string path, vector<string>& result) {
path += to_string(cur->val); // 中
if (cur->left == nullptr && cur->right == nullptr) {
result.push_back(path);
return;
}
if (cur->left) traversal(cur->left, path + "->", result); // 左
if (cur->right) traversal(cur->right, path + "->", result); // 右
}
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> result;
string path;
if (root == nullptr) { return result; }
traversal(root, path, result);
return result;
}
};
Problem: Given the root of a binary tree, return the sum of all left leaves. A leaf is a node with no children. A left leaf is a leaf that is the left child of another node.
Case 1: Input: root = [3,9,20,null,null,15,7], Output: 24
Case 2: Input: root = [1], Output: 0
/**
* 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 sumOfLeftLeaves(TreeNode* root) {
if (root == nullptr) { return 0; }
if (root->left == nullptr && root->right== nullptr) { return 0; }
int leftValue = sumOfLeftLeaves(root->left); // 左
// 左子树就是一个左叶子的情况
if (root->left && !root->left->left && !root->left->right) {
leftValue = root->left->val;
}
int rightValue = sumOfLeftLeaves(root->right); // 右
int sum = leftValue + rightValue; // 中
return sum;
}
};
// 精简版
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if (root == nullptr) { return 0; }
int leftValue = 0;
if (root->left != nullptr && root->left->left == nullptr && root->left->right == nullptr) {
leftValue = root->left->val;
}
return leftValue + sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
}
};
21. 513. Find Bottom Left Tree Value
Problem: Given the root of a binary tree, return the leftmost value in the last row of the tree.
Case 1: Input: root = [2,1,3], Output: 1
Case 2: Input: root = [1,2,3,4,null,5,6,null,null,7], Output: 7
/**
* 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) {}
* };
*/
// Recursive Method
class Solution {
public:
int result;
int maxDepth = INT_MIN;
void traversal(TreeNode* root, int depth) {
if (root->left == nullptr && root->right == nullptr) {
if (depth > maxDepth) {
maxDepth = depth;
result = root->val;
}
return;
}
if (root->left) {
depth++;
traversal(root->left, depth);
depth--; // 回溯
}
if (root->right) {
depth++;
traversal(root->right, depth);
depth--; // 回溯
}
return;
}
int findBottomLeftValue(TreeNode* root) {
traversal(root, 0);
return result;
}
};
// 精简写法
class Solution {
public:
int result;
int maxDepth = INT_MIN;
void traversal(TreeNode* root, int depth) {
if (root->left == nullptr && root->right == nullptr) {
if (depth > maxDepth) {
maxDepth = depth;
result = root->val;
}
return;
}
if (root->left) {
traversal(root->left, depth + 1); // 隐藏着回溯
}
if (root->right) {
traversal(root->right, depth + 1); // 隐藏着回溯
}
return;
}
int findBottomLeftValue(TreeNode* root) {
traversal(root, 0);
return result;
}
};
// Layer Traversal
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> que;
if (root != nullptr) { que.push(root); }
int result = 0;
while (!que.empty()) {
int size = que.size();
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
// 记录最后一行第一个元素
if (i == 0) { result = node->val; }
if (node->left) { que.push(node->left); }
if (node->right) { que.push(node->right); }
}
}
return result;
}
};
22. 112. Path Sum
Problem: Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum. A leaf is a node with no children.
Case 1: Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22, Output: true
Explanation: The root-to-leaf path with the target sum is shown.
Case 2: Input: root = [1,2,3], targetSum = 5, Output: false
Explanation: There two root-to-leaf paths in the tree:
(1 -> 2): The sum is 3
(1 -> 3): The sum is 4
There is no root-to-leaf path with sum = 5
Case 3: Input: root = [], targetSum = 0, Output: false
/**
* 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) {}
* };
*/
// Recursive Method
class Solution {
private:
bool traversal(TreeNode* cur, int count) {
// 遇到叶子节点, 并且计数为0
if (!cur->left && !cur->right && count == 0) { return true; }
// 遇到叶子节点直接返回
if (!cur->left && !cur->right) { return false; }
// 左
if (cur->left) {
// 递归, 处理节点
count -= cur->left->val;
if (traversal(cur->left, count)) { return true; }
// 回溯, 撤销处理结果
count += cur->left->val;
}
// 右
if (cur->right) {
// 递归, 处理节点
count -= cur->right->val;
if (traversal(cur->right, count)) { return true; }
// 回溯, 撤销处理结果
count += cur->right->val;
}
return false;
}
public:
bool hasPathSum(TreeNode* root, int sum) {
if (root == nullptr) { return false; }
return traversal(root, sum - root->val);
}
};
// 精简写法
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
if (root == nullptr) { return false; }
if (!root->left && !root->right && sum == root->val) {
return true;
}
return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
}
};
// Iterative Method
// 此时栈里一个元素不仅要记录该节点指针, 还要记录从头结点到该节点的路径数值总和
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
if (root == nullptr) { return false; }
// 此时栈里要放的是pair<节点指针, 路径数值>
stack<pair<TreeNode*, int>> st;
st.push(pair<TreeNode*, int>(root, root->val));
while (!st.empty()) {
pair<TreeNode*, int> node = st.top();
st.pop();
// 如果该节点是叶子节点了, 同时该节点的路径数值等于sum, 那么就返回true
if (!node.first->left && !node.first->right && sum == node.second) { return true; }
// 右节点, 压进去一个节点的时候, 将该节点的路径数值也记录下来
if (node.first->right) {
st.push(pair<TreeNode*, int>(node.first->right, node.second + node.first->right->val));
}
// 左节点, 压进去一个节点的时候, 将该节点的路径数值也记录下来
if (node.first->left) {
st.push(pair<TreeNode*, int>(node.first->left, node.second + node.first->left->val));
}
}
return false;
}
};
23. 113. Path Sum II
Problem: Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references. A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.
Case 1: Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22
Case 2: Input: root = [1,2,3], targetSum = 5, Output: []
Case 3: Input: root = [1,2], targetSum = 0, Output: []
/**
* 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) {}
* };
*/
// Recursive Method
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
// 要遍历整个树, 找到所有路径, 所以递归函数不要返回值
void traversal(TreeNode* cur, int count) {
// 遇到了叶子节点且找到了和为targetSum的路径
if (!cur->left && !cur->right && count == 0) {
result.push_back(path);
return;
}
// 遇到叶子节点而没有找到合适的边, 直接返回
if (!cur->left && !cur->right) {
return;
}
// 左 (空节点不遍历)
if (cur->left) {
path.push_back(cur->left->val);
count -= cur->left->val;
traversal(cur->left, count); // 递归
count += cur->left->val; // 回溯
path.pop_back(); // 回溯
}
// 右 (空节点不遍历)
if (cur->right) {
path.push_back(cur->right->val);
count -= cur->right->val;
traversal(cur->right, count); // 递归
count += cur->right->val; // 回溯
path.pop_back(); // 回溯
}
return ;
}
public:
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
result.clear();
path.clear();
if (root == nullptr) { return result; }
// 把根节点放进路径
path.push_back(root->val);
traversal(root, targetSum - root->val);
return result;
}
};
24. 106. Construct Binary Tree from Inorder and Postorder Traversal
Problem: Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.
Case 1: Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3], Output: [3,9,20,null,null,15,7]
Case 2: Input: inorder = [-1], postorder = [-1], Output: [-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) {}
* };
*/
// (1) 如果数组大小为零的话, 说明是空节点了
// (2) 如果不为空, 那么取后序数组最后一个元素作为节点元素
// (3) 找到后序数组最后一个元素在中序数组的位置, 作为切割点
// (4) 切割中序数组, 切成中序左数组和中序右数组 (顺序别搞反了, 一定是先切中序数组)
// (5) 切割后序数组, 切成后序左数组和后序右数组
// (6) 递归处理左区间和右区间
class Solution {
private:
TreeNode* traversal (vector<int>& inorder, vector<int>& postorder) {
if (postorder.size() == 0) { return nullptr; }
// 后序遍历数组最后一个元素, 就是当前的中间节点
int rootValue = postorder[postorder.size() - 1];
TreeNode* root = new TreeNode(rootValue);
// 叶子节点
if (postorder.size() == 1) { return root; }
// 找到中序遍历的切割点
int delimiterIndex;
for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {
if (inorder[delimiterIndex] == rootValue) { break; }
}
// 切割中序数组
// 左闭右开区间
// 左中序数组 ：[0, delimiterIndex)
// 右中序数组 ：[delimiterIndex + 1, end)
vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end());
// postorder 舍弃末尾元素
postorder.resize(postorder.size() - 1);
// 切割后序数组
// 依然左闭右开, 注意这里使用了左中序数组大小作为切割点
// 左后序数组 : [0, leftInorder.size())
// 右后序数组 ：[leftInorder.size(), end)
vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());
root->left = traversal(leftInorder, leftPostorder);
root->right = traversal(rightInorder, rightPostorder);
return root;
}
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (inorder.size() == 0 || postorder.size() == 0) { return nullptr; };
return traversal(inorder, postorder);
}
};
// 优化版本
class Solution {
private:
// 中序区间: [inorderBegin, inorderEnd)
// 后序区间: [postorderBegin, postorderEnd)
TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd,
vector<int>& postorder, int postorderBegin, int postorderEnd) {
if (postorderBegin == postorderEnd) { return nullptr; }
int rootValue = postorder[postorderEnd - 1];
TreeNode* root = new TreeNode(rootValue);
if (postorderEnd - postorderBegin == 1) { return root; }
int delimiterIndex;
for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {
if (inorder[delimiterIndex] == rootValue) { break; }
}
// 切割中序数组
// 左中序区间, 左闭右开: [leftInorderBegin, leftInorderEnd)
int leftInorderBegin = inorderBegin;
int leftInorderEnd = delimiterIndex;
// 右中序区间, 左闭右开: [rightInorderBegin, rightInorderEnd)
int rightInorderBegin = delimiterIndex + 1;
int rightInorderEnd = inorderEnd;
// 切割后序数组
// 左后序区间, 左闭右开: [leftPostorderBegin, leftPostorderEnd)
int leftPostorderBegin = postorderBegin;
// 终止位置需要加上中序区间的大小size
int leftPostorderEnd = postorderBegin + delimiterIndex - inorderBegin;
// 右后序区间, 左闭右开: [rightPostorderBegin, rightPostorderEnd)
int rightPostorderBegin = postorderBegin + (delimiterIndex - inorderBegin);
int rightPostorderEnd = postorderEnd - 1; // 排除最后一个元素, 已经作为节点了
root->left = traversal(inorder, leftInorderBegin, leftInorderEnd,
postorder, leftPostorderBegin, leftPostorderEnd);
root->right = traversal(inorder, rightInorderBegin, rightInorderEnd,
postorder, rightPostorderBegin, rightPostorderEnd);
return root;
}
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (inorder.size() == 0 || postorder.size() == 0) { return nullptr; }
// 左闭右开的原则
return traversal(inorder, 0, inorder.size(), postorder, 0, postorder.size());
}
};
25. 105. Construct Binary Tree from Preorder and Inorder Traversal
Problem: Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.
Case 1: Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7], Output: [3,9,20,null,null,15,7]
Case 2: Input: preorder = [-1], inorder = [-1], Output: [-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 {
private:
TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd,
vector<int>& preorder, int preorderBegin, int preorderEnd) {
if (preorderBegin == preorderEnd) { return nullptr; }
// 注意用preorderBegin 不要用0
int rootValue = preorder[preorderBegin];
TreeNode* root = new TreeNode(rootValue);
if (preorderEnd - preorderBegin == 1) { return root; }
int delimiterIndex;
for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {
if (inorder[delimiterIndex] == rootValue) { break; }
}
// 切割中序数组
// 中序左区间, 左闭右开: [leftInorderBegin, leftInorderEnd)
int leftInorderBegin = inorderBegin;
int leftInorderEnd = delimiterIndex;
// 中序右区间, 左闭右开: [rightInorderBegin, rightInorderEnd)
int rightInorderBegin = delimiterIndex + 1;
int rightInorderEnd = inorderEnd;
// 切割前序数组
// 前序左区间, 左闭右开: [leftPreorderBegin, leftPreorderEnd)
int leftPreorderBegin = preorderBegin + 1;
// 终止位置是起始位置加上中序左区间的大小size
int leftPreorderEnd = preorderBegin + 1 + delimiterIndex - inorderBegin;
// 前序右区间, 左闭右开: [rightPreorderBegin, rightPreorderEnd)
int rightPreorderBegin = preorderBegin + 1 + (delimiterIndex - inorderBegin);
int rightPreorderEnd = preorderEnd;
root->left = traversal(inorder, leftInorderBegin, leftInorderEnd,
preorder, leftPreorderBegin, leftPreorderEnd);
root->right = traversal(inorder, rightInorderBegin, rightInorderEnd,
preorder, rightPreorderBegin, rightPreorderEnd);
return root;
}
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if (inorder.size() == 0 || preorder.size() == 0) { return nullptr; }
// 参数坚持左闭右开的原则
return traversal(inorder, 0, inorder.size(), preorder, 0, preorder.size());
}
};
Problem: You are given an integer array nums with no duplicates. A maximum binary tree can be built recursively from nums using the following algorithm:
(1) Create a root node whose value is the maximum value in nums.
(2) Recursively build the left subtree on the subarray prefix to the left of the maximum value.
(3) Recursively build the right subtree on the subarray suffix to the right of the maximum value.
(4) Return the maximum binary tree built from nums.
Case 1: Input: nums = [3,2,1,6,0,5], Output: [6,3,5,null,2,0,null,null,1]
Case 2: Input: nums = [3,2,1], Output: [3,null,2,null,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) {}
* };
*/
// Recursive Method - Preorder Traversal
class Solution {
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
TreeNode* node = new TreeNode(0);
// 根节点或叶子节点
if (nums.size() == 1) {
node->val = nums[0];
return node;
}
// 找到数组中最大的值和对应的下标
int maxValue = 0;
int maxValueIndex = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] > maxValue) {
maxValue = nums[i];
maxValueIndex = i;
}
}
node->val = maxValue;
// 构造左子树: 最大值所在的下标左区间
if (maxValueIndex > 0) {
vector<int> newVec(nums.begin(), nums.begin() + maxValueIndex);
node->left = constructMaximumBinaryTree(newVec);
}
// 构造右子树: 最大值所在的下标右区间
if (maxValueIndex < (nums.size() - 1)) {
vector<int> newVec(nums.begin() + maxValueIndex + 1, nums.end());
node->right = constructMaximumBinaryTree(newVec);
}
return node;
}
};
// 精简版
class Solution {
private:
// 在左闭右开区间[left, right), 构造二叉树
TreeNode* traversal(vector<int>& nums, int left, int right) {
if (left >= right) { return nullptr; }
// 分割点下标: maxValueIndex
int maxValueIndex = left;
for (int i = left + 1; i < right; ++i) {
if (nums[i] > nums[maxValueIndex]) { maxValueIndex = i; }
}
TreeNode* root = new TreeNode(nums[maxValueIndex]);
// 左闭右开: [left, maxValueIndex)
root->left = traversal(nums, left, maxValueIndex);
// 左闭右开: [maxValueIndex + 1, right)
root->right = traversal(nums, maxValueIndex + 1, right);
return root;
}
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
return traversal(nums, 0, nums.size());
}
};
27. 617. Merge Two Binary Trees
Problem: You are given two binary trees root1 and root2. Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree. Return the merged tree. Note: The merging process must start from the root nodes of both trees.
Case 1: Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7], Output: [3,4,5,5,4,null,7]
Case 2: Input: root1 = [1], root2 = [1,2], Output: [2,2]
/**
* 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) {}
* };
*/
// Recursive Method - Preorder Traversal
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if (root1 == nullptr) { return root2; } // 如果t1为空, 合并之后就应该是t2
if (root2 == nullptr) { return root1; } // 如果t2为空, 合并之后就应该是t1
// 修改了t1的数值和结构
root1->val += root2->val; // 中
root1->left = mergeTrees(root1->left, root2->left); // 左
root1->right = mergeTrees(root1->right, root2->right); // 右
return root1;
}
};
// Recursive Method - Preorder Traversal
// Construct a new tree
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if (root1 == nullptr) { return root2; }
if (root2 == nullptr) { return root1; }
// 重新定义新的节点, 不修改原有两个树的结构
TreeNode* root = new TreeNode(0);
root->val = root1->val + root2->val; // 中
root->left = mergeTrees(root1->left, root2->left); // 左
root->right = mergeTrees(root1->right, root2->right); // 右
return root;
}
};
// Recursive Method - Inorder Traversal
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if (root1 == nullptr) { return root2; } // 如果t1为空, 合并之后就应该是t2
if (root2 == nullptr) { return root1; } // 如果t2为空, 合并之后就应该是t1
// 修改了t1的数值和结构
root1->left = mergeTrees(root1->left, root2->left); // 左
root1->val += root2->val; // 中
root1->right = mergeTrees(root1->right, root2->right); // 右
return root1;
}
};
// Recursive Method - Postorder Traversal
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if (root1 == nullptr) { return root2; } // 如果t1为空, 合并之后就应该是t2
if (root2 == nullptr) { return root1; } // 如果t2为空, 合并之后就应该是t1
// 修改了t1的数值和结构
root1->left = mergeTrees(root1->left, root2->left); // 左
root1->right = mergeTrees(root1->right, root2->right); // 右
root1->val += root2->val; // 中
return root1;
}
};
28. 700. Search in a Binary Search Tree
Problem: You are given the root of a binary search tree (BST) and an integer val. Find the node in the BST that the node’s value equals val and return the subtree rooted with that node. If such a node does not exist, return null.
Case 1: Input: root = [4,2,7,1,3], val = 2, Output: [2,1,3]
Case 2: Input: root = [4,2,7,1,3], val = 5, Output: []
/**
* 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) {}
* };
*/
// Recursive Method
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
if (root == nullptr || root->val == val) { return root; }
TreeNode* result = nullptr;
if (root->val > val) { result = searchBST(root->left, val); }
if (root->val < val) { result = searchBST(root->right, val); }
return result;
}
};
// Recursive Method
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
if (root == nullptr || root->val == val) { return root; }
if (root->val > val) { return searchBST(root->left, val); }
if (root->val < val) { return searchBST(root->right, val); }
return nullptr;
}
};
// Iterative Method
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
while (root != nullptr) {
if (root->val > val) { root = root->left; }
else if (root->val < val) { root = root->right; }
else { return root; }
}
return nullptr;
}
};
29. 98. Validate Binary Search Tree
Problem: Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as follows:
(1) The left subtree of a node contains only nodes with keys less than the node’s key.
(2) The right subtree of a node contains only nodes with keys greater than the node’s key.
(3) Both the left and right subtrees must also be binary search trees.
Case 1: Input: root = [2,1,3], Output: true
Case 2: Input: root = [5,1,4,null,null,3,6], Output: false
/**
* 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 {
private:
vector<int> vec;
void traversal(TreeNode* root) {
if (root == nullptr) { return; }
traversal(root->left); // 左
// 将二叉搜索树转换为有序数组
vec.push_back(root->val); // 中
traversal(root->right); // 右
}
public:
bool isValidBST(TreeNode* root) {
vec.clear();
traversal(root);
for (int i = 1; i < vec.size(); i++) {
// 注意要小于等于, 搜索树里不能有相同元素
if (vec[i] <= vec[i - 1]) { return false; }
}
return true;
}
};
// Recursive Method
class Solution {
public:
// 因为后台测试数据中有int最小值
long long maxVal = LONG_MIN;
bool isValidBST(TreeNode* root) {
if (root == nullptr) { return true; }
bool left = isValidBST(root->left); // 左
// 中序遍历, 验证遍历的元素是不是从小到大
if (maxVal < root->val) { maxVal = root->val; } // 中
else { return false; }
bool right = isValidBST(root->right); // 右
return left && right;
}
};
// Recursive Method
class Solution {
public:
// 用来记录前一个节点
TreeNode* pre = nullptr;
bool isValidBST(TreeNode* root) {
if (root == nullptr) { return true; }
bool left = isValidBST(root->left); // 左
if (pre != nullptr && pre->val >= root->val) { // 中
return false;
}
// 记录前一个节点
pre = root;
bool right = isValidBST(root->right); // 右
return left && right;
}
};
30. 530. Minimum Absolute Difference in BST
Problem: Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.
Case 1: Input: root = [4,2,6,1,3], Output: 1
Case 2: Input: root = [1,0,48,null,null,12,49], Output: 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) {}
* };
*/
// Recursive Method - Inorder Traversal
class Solution {
private:
int result = INT_MAX;
TreeNode* pre = nullptr;
void traversal(TreeNode* cur) {
if (cur == nullptr) { return; }
traversal(cur->left); // 左
if (pre != nullptr){ // 中
result = min(result, cur->val - pre->val);
}
pre = cur; // Updata pre
traversal(cur->right); // 右
}
public:
int getMinimumDifference(TreeNode* root) {
traversal(root);
return result;
}
};
// 二叉搜索树可是有序的, 在一个有序数组上求两个数最小差值
class Solution {
private:
vector<int> vec;
void traversal(TreeNode* root) {
if (root == nullptr) { return; }
traversal(root->left); // 左
// 将二叉搜索树转换为有序数组 // 中
vec.push_back(root->val); // 右
traversal(root->right);
}
public:
int getMinimumDifference(TreeNode* root) {
vec.clear();
traversal(root);
if (vec.size() < 2) { return 0; }
int result = INT_MAX;
// 统计有序数组的最小差值
for (int i = 1; i < vec.size(); i++) {
result = min(result, vec[i] - vec[i-1]);
}
return result;
}
};
// Iterative Method - Inorder Traversal
class Solution {
public:
int getMinimumDifference(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* cur = root;
TreeNode* pre = nullptr;
int result = INT_MAX;
while (cur != nullptr || !st.empty()) {
// 指针来访问节点, 访问到最底层
if (cur != nullptr) {
// 将访问的节点放进栈
st.push(cur);
cur = cur->left; // 左
} else {
cur = st.top();
st.pop();
if (pre != nullptr) { // 中
result = min(result, cur->val - pre->val);
}
pre = cur;
cur = cur->right; // 右
}
}
return result;
}
};
31. 501. Find Mode in Binary Search Tree
Problem: Given the root of a binary search tree (BST) with duplicates, return all the mode(s) (i.e., the most frequently occurred element) in it. If the tree has more than one mode, return them in any order. Assume a BST is defined as follows:
(1) The left subtree of a node contains only nodes with keys less than or equal to the node’s key.
(2) The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
(3) Both the left and right subtrees must also be binary search trees.
Case 1: Input: root = [1,null,2,2], Output: [2]
Case 2: Input: root = [0], Output: [0]
/**
* 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) {}
* };
*/
// Recursive Method - Inorder Traversal
class Solution {
private:
int count = 0; // 统计单个元素频率
int maxCount = 0; // 记录最大元素频率
TreeNode* pre = nullptr;
vector<int> result;
void searchBST(TreeNode* cur) {
if (cur == nullptr) { return ; }
searchBST(cur->left); // 左
if (pre == nullptr) { // 中, 第一个节点
count = 1;
} else if (pre->val == cur->val) { // 与前一个节点数值相同
count++;
} else { // 与前一个节点数值不同
count = 1;
}
pre = cur; // 更新上一个节点
if (count == maxCount) { // 如果和最大值相同, 放进result中
result.push_back(cur->val);
}
if (count > maxCount) { // 如果计数大于最大值频率
maxCount = count; // 更新最大频率
result.clear(); // 清空result, 之前result里的元素都失效了
result.push_back(cur->val);
}
searchBST(cur->right); // 右
return ;
}
public:
vector<int> findMode(TreeNode* root) {
count = 0;
maxCount = 0;
TreeNode* pre = nullptr; // 记录前一个节点
result.clear();
searchBST(root);
return result;
}
};
// Iterative Method - Inorder Traversal
class Solution {
public:
vector<int> findMode(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* cur = root;
TreeNode* pre = nullptr;
int count = 0; // 统计单个元素频率
int maxCount = 0; // 记录最大元素频率
vector<int> result;
while (cur != nullptr || !st.empty()) {
if (cur != nullptr) { // 指针来访问节点, 访问到最底层
st.push(cur); // 将访问的节点放进栈
cur = cur->left; // 左
} else {
cur = st.top();
st.pop(); // 中
if (pre == NULL) { // 第一个节点
count = 1;
} else if (pre->val == cur->val) { // 与前一个节点数值相同
count++;
} else { // 与前一个节点数值不同
count = 1;
}
if (count == maxCount) { // 如果和最大值相同, 放进result中
result.push_back(cur->val);
}
if (count > maxCount) { // 如果计数大于最大值频率
maxCount = count; // 更新最大频率
result.clear(); // 清空result, 之前result里的元素都失效了
result.push_back(cur->val);
}
pre = cur;
cur = cur->right; // 右
}
}
return result;
}
};
// Recursive Method for all BT not only BST
class Solution {
private:
void searchBST(TreeNode* cur, unordered_map<int, int>& map) {
// 前序遍历
if (cur == nullptr) { return; }
// 统计元素频率
map[cur->val]++;
searchBST(cur->left, map);
searchBST(cur->right, map);
return ;
}
bool static cmp (const pair<int, int>& a, const pair<int, int>& b) {
return a.second > b.second;
}
public:
vector<int> findMode(TreeNode* root) {
// key: 元素, value: 出现频率
unordered_map<int, int> map;
vector<int> result;
if (root == nullptr) { return result; }
searchBST(root, map);
vector<pair<int, int>> vec(map.begin(), map.end());
// 给频率排个序
sort(vec.begin(), vec.end(), cmp);
result.push_back(vec[0].first);
for (int i = 1; i < vec.size(); i++) {
// 取最高的放到result数组中
if (vec[i].second == vec[0].second) result.push_back(vec[i].first);
else break;
}
return result;
}
};
32. 236. Lowest Common Ancestor of a Binary Tree
Problem: Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. According to the definition of LCA on Wikipedia: The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).
Case 1: Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1, Output: 3
Case 2: Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4, Output: 5
Case 2: Input: root = [1,2], p = 1, q = 2, Output: 1
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
// Recursive Method - Postorder Traversal
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == q || root == p || root == nullptr) { return root; }
TreeNode* left = lowestCommonAncestor(root->left, p, q); // 左
TreeNode* right = lowestCommonAncestor(root->right, p, q); // 右
if (left != nullptr && right != nullptr) { return root; } // 中
if (left == nullptr && right != nullptr) { return right; } // 中
else if (left != nullptr && right == nullptr) { return left; } // 中
else { // (left == nullptr && right == nullptr)
return nullptr;
}
}
};
// 精简版
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == q || root == p || root == nullptr) { return root; }
TreeNode* left = lowestCommonAncestor(root->left, p, q); // 左
TreeNode* right = lowestCommonAncestor(root->right, p, q); // 右
if (left != nullptr && right != nullptr) { return root; } // 中
if (left == nullptr) { return right; } // 中
return left;
}
};
33. 235. Lowest Common Ancestor of a Binary Search Tree
Problem: Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST. According to the definition of LCA on Wikipedia: The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).
Case 1: Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8, Output: 6
Case 2: Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4, Output: 2
Case 3: Input: root = [2,1], p = 2, q = 1, Output: 2
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
// Recursive Method
class Solution {
private:
TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q) {
if (cur == nullptr) { return cur; }
// 中
if (cur->val > p->val && cur->val > q->val) { // 左
TreeNode* left = traversal(cur->left, p, q);
if (left != nullptr) {
return left;
}
}
if (cur->val < p->val && cur->val < q->val) { // 右
TreeNode* right = traversal(cur->right, p, q);
if (right != nullptr) {
return right;
}
}
// (cur->val > p->val && cur->val < q->val) or
// (cur->val < p->val && cur->val > q->val)
return cur;
}
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
return traversal(root, p, q);
}
};
// 精简版
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root->val > p->val && root->val > q->val) {
return lowestCommonAncestor(root->left, p, q);
} else if (root->val < p->val && root->val < q->val) {
return lowestCommonAncestor(root->right, p, q);
} else { return root; }
}
};
// Iterative Method
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
while(root) {
if (root->val > p->val && root->val > q->val) {
root = root->left;
} else if (root->val < p->val && root->val < q->val) {
root = root->right;
} else { return root; }
}
return nullptr;
}
};
34. 701. Insert into a Binary Search Tree
Problem: You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST. Notice that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.
Case 1: Input: root = [4,2,7,1,3], val = 5, Output: [4,2,7,1,3,5]
Case 2: Input: root = [40,20,60,10,30,50,70], val = 25, Output: [40,20,60,10,30,50,70,null,null,25]
Case 3: Input: root = [4,2,7,1,3,null,null,null,null,null,null], val = 5, Output: [4,2,7,1,3,5]
/**
* 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) {}
* };
*/
// Recursive Method
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (root == nullptr) {
TreeNode* node = new TreeNode(val);
return node;
}
if (root->val > val) { root->left = insertIntoBST(root->left, val); }
if (root->val < val) { root->right = insertIntoBST(root->right, val); }
return root;
}
};
// Iterative Method
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (root == nullptr) {
TreeNode* node = new TreeNode(val);
return node;
}
TreeNode* cur = root;
TreeNode* parent = root; // 需要记录上一个节点, 否则无法赋值新节点
while (cur != nullptr) {
parent = cur;
if (cur->val > val) { cur = cur->left; }
else { cur = cur->right; }
}
TreeNode* node = new TreeNode(val);
// 此时是用parent节点的进行赋值
if (val < parent->val) { parent->left = node; }
else { parent->right = node; }
return root;
}
};
Problem: Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST. Basically, the deletion can be divided into two stages: Search for a node to remove. If the node is found, delete the node.
Case 1: Input: root = [5,3,6,2,4,null,7], key = 3, Output: [5,4,6,2,null,null,7]
Case 2: Input: root = [5,3,6,2,4,null,7], key = 0, Output: [5,3,6,2,4,null,7]
Case 3: Input: root = [], key = 0, Output: []
/**
* 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) {}
* };
*/
// Recursive Method
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
// 第一种情况: 没找到删除的节点, 遍历到空节点直接返回了
if (root == nullptr) { return root; }
// 终止条件
if (root->val == key) {
// 第二种情况: 左右孩子都为空(叶子节点), 直接删除节点, 返回NULL为根节点
if (root->left == nullptr && root->right == nullptr) {
// 内存释放
delete root;
return nullptr;
}
// 第三种情况: 其左孩子为空, 右孩子不为空, 删除节点, 右孩子补位, 返回右孩子为根节点
else if (root->left == nullptr) {
auto retNode = root->right;
// 内存释放
delete root;
return retNode;
}
// 第四种情况: 其右孩子为空, 左孩子不为空, 删除节点, 左孩子补位, 返回左孩子为根节点
else if (root->right == nullptr) {
auto retNode = root->left;
// 内存释放
delete root;
return retNode;
}
// 第五种情况: 左右孩子节点都不为空, 将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置
// 并返回删除节点右孩子为新的根节点
else {
TreeNode* cur = root->right; // 找右子树最左面的节点
while(cur->left != nullptr) {
cur = cur->left;
}
cur->left = root->left; // 把要删除的节点(root)左子树放在cur的左孩子的位置
TreeNode* tmp = root; // 把root节点保存一下, 下面来删除
root = root->right; // 返回旧root的右孩子作为新root
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;
}
};
// Iterative Method
class Solution {
private:
// 将目标节点(删除节点)的左子树放到, 目标节点的右子树的最左面节点的左孩子位置上
// 并返回目标节点右孩子为新的根节点
TreeNode* deleteOneNode(TreeNode* target) {
if (target == nullptr) { return target; }
if (target->right == nullptr) { return target->left; }
TreeNode* cur = target->right;
while (cur->left) {
cur = cur->left;
}
cur->left = target->left;
return target->right;
}
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == nullptr) { return root; }
TreeNode* cur = root;
// 记录cur的父节点, 用来删除cur
TreeNode* pre = nullptr;
while (cur) {
if (cur->val == key) { break; }
pre = cur;
if (cur->val > key) { cur = cur->left; }
else { cur = cur->right; }
}
// 如果搜索树只有头结点
if (pre == nullptr) {
return deleteOneNode(cur);
}
// pre 要知道是删左孩子还是右孩子
if (pre->left && pre->left->val == key) {
pre->left = deleteOneNode(cur);
}
if (pre->right && pre->right->val == key) {
pre->right = deleteOneNode(cur);
}
return root;
}
};
36. 669. Trim a Binary Search Tree
Problem: Given the root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lies in [low, high]. Trimming the tree should not change the relative structure of the elements that will remain in the tree (i.e., any node’s descendant should remain a descendant). It can be proven that there is a unique answer. Return the root of the trimmed binary search tree. Note that the root may change depending on the given bounds.
Case 1: Input: root = [1,0,2], low = 1, high = 2, Output: [1,null,2]
Case 2: Input: root = [3,0,4,null,2,null,null,1], low = 1, high = 3, Output: [3,2,null,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) {}
* };
*/
// Recursive Method
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int low, int high) {
if (root == nullptr ) { return nullptr; }
// 寻找符合区间[low, high]的节点
if (root->val < low) {
TreeNode* right = trimBST(root->right, low, high);
return right;
}
// 寻找符合区间[low, high]的节点
if (root->val > high) {
TreeNode* left = trimBST(root->left, low, high);
return left;
}
root->left = trimBST(root->left, low, high); // root->left接入符合条件的左孩子
root->right = trimBST(root->right, low, high); // root->right接入符合条件的右孩子
return root;
}
};
// 精简版
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int low, int high) {
if (root == nullptr) { return nullptr; }
if (root->val < low) { return trimBST(root->right, low, high); }
if (root->val > high) { return trimBST(root->left, low, high); }
root->left = trimBST(root->left, low, high);
root->right = trimBST(root->right, low, high);
return root;
}
};
37. 108. Convert Sorted Array to Binary Search Tree
Problem: Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.
Case 1: Input: nums = [-10,-3,0,5,9], Output: [0,-3,9,-10,null,5]
Case 2: Input: nums = [1,3], Output: [3,1]
Explanation: [1,null,3] and [3,1] are both height-balanced BSTs.
/**
* 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) {}
* };
*/
// Recursive Method
class Solution {
private:
TreeNode* traversal(vector<int>& nums, int left, int right) {
if (left > right) { return nullptr; }
int mid = left + ((right - left) / 2);
TreeNode* root = new TreeNode(nums[mid]);
root->left = traversal(nums, left, mid - 1);
root->right = traversal(nums, mid + 1, right);
return root;
}
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
// [0, nums.size()-1]
TreeNode* root = traversal(nums, 0, nums.size() - 1);
return root;
}
};
38. 538. Convert BST to Greater Tree
Problem: Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST.
As a reminder, a binary search tree is a tree that satisfies these constraints:
(1) The left subtree of a node contains only nodes with keys less than the node’s key.
(2) The right subtree of a node contains only nodes with keys greater than the node’s key.
(3) Both the left and right subtrees must also be binary search trees.
Case 1: Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
Case 2: Input: root = [0,null,1], Output: [1,null,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 {
private:
// 记录前一个节点的数值
int pre = 0;
void traversal(TreeNode* cur) { // 右中左遍历
if (cur == nullptr) { return; }
traversal(cur->right); // 右
cur->val += pre; // 中
pre = cur->val;
traversal(cur->left); // 左
}
public:
TreeNode* convertBST(TreeNode* root) {
pre = 0;
traversal(root);
return root;
}
};