Binary Tree C++
[1]:
import IPython; IPython.display.HTML('''<script>code_show=true; function code_toggle() { if (code_show){ $('div.nbinput').show(); } else { $('div.nbinput').hide(); } code_show = !code_show} $( document ).ready(code_toggle);</script><form action="javascript:code_toggle()"><input type="submit" value="Click here to toggle on/off the raw code."></form>''')
[1]:
104. Maximum Depth of Binary Tree
Easy
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.
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: 3
Constraints:
The number of nodes in the tree is in the range [0, 104].
-100 <= Node.val <= 100
[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
#include <algorithm> // std::max
int maxDepth(TreeNode* root) {
if(root)
return 1 + std::max(maxDepth(root->left), maxDepth(root->right));
else
return 0;
}
[ ]:
// BFS: 進 for 迴圈之前一定要把 q.size() copy 出來，不然在迴圈裡改 q 的內容時 size 會一直變
#include <deque>
int maxDepth(TreeNode* root) {
std::deque<TreeNode*> q;
if (root)
q.push_back(root);
int depth = 0;
while (q.size())
{
int size = q.size();
for (size_t i=0 ; i<size ; i++)
{
TreeNode* node = q.front();
q.pop_front();
if (node->left)
q.push_back(node->left);
if (node->right)
q.push_back(node->right);
}
depth++;
}
return depth;
}
110. Balanced Binary Tree
Easy
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as:
a binary tree in which the left and right subtrees of every node differ in height by no more than 1.
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: true
Constraints:
The number of nodes in the tree is in the range [0, 5000].
-10^4 <= Node.val <= 10^4
[ ]:
// std::tuple + structured binding (available since C++17), 也可以不用 tuple 用 pair，定義在 <utility>
#include <tuple> // std::tuple
#include <algorithm> // std::max
#include <cmath> // std::abs
std::tuple<int, bool> depth_balanced(const TreeNode* const root){
if (root)
{
auto [depth_l, balanced_l] = depth_balanced(root->left);
auto [depth_r, balanced_r] = depth_balanced(root->right);
return {1 + std::max(depth_l, depth_r), balanced_l and balanced_r and std::abs(depth_l - depth_r) < 2};
}
else
{
return {0, true};
}
}
[3]:
bool isBalanced(TreeNode* root) {
auto [depth, balanced] = depth_balanced(root);
return balanced;
}
124. Binary Tree Maximum Path Sum
Hard
A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.
The path sum of a path is the sum of the node’s values in the path.
Given the root of a binary tree, return the maximum path sum of any path.
Example 2:
Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.
Constraints:
The number of nodes in the tree is in the range [1, 3*10^4].
-1000 <= Node.val <= 1000
[ ]:
#include <tuple> // std::tuple
#include <algorithm> // std::max
std::tuple<int, int> mps(const TreeNode* const root){
if (root)
{
auto [sum_l, rsum_l] = mps(root->left);
auto [sum_r, rsum_r] = mps(root->right);
int rsum = std::max({root->val, root->val + rsum_l, root->val + rsum_r});
return {std::max({sum_l, sum_r, rsum, root->val + rsum_l + rsum_r}), rsum};
}
else
{
return {-100000, -100000};
}
}
[ ]:
int maxPathSum(TreeNode* root) {
auto [sum, rsum] = mps(root);
return sum;
}
236. Lowest Common Ancestor of a Binary Tree
Medium
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).”
Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
Constraints:
The number of nodes in the tree is in the range [2, 10^5].
-10^9 <= Node.val <= 10^9
All Node.val are unique.
p != q
p and q will exist in the tree.
[3]:
// DFS 從下向上（divide and conquer 先遞迴傳回結果再合併）
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root==p or root==q or root==nullptr)
return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left && right)
return root;
else if (left)
return left;
else
return right;
}
102. Binary Tree Level Order Traversal
Medium
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).
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
Constraints:
The number of nodes in the tree is in the range [0, 2000].
-1000 <= Node.val <= 1000
[ ]:
// c++ deque 的 pop 不會回傳 popped element！
#include <vector>
#include <deque>
std::vector<std::vector<int>> levelOrder(TreeNode* root) {
std::deque<TreeNode*> q;
if (root)
q.push_back(root);
std::vector<std::vector<int>> res;
while (q.size())
{
std::vector<int> level;
int size = q.size();
for (size_t i=0 ; i<size ; i++)
{
TreeNode* node = q.front();
q.pop_front();
level.push_back(node->val);
if (node->left)
q.push_back(node->left);
if (node->right)
q.push_back(node->right);
}
res.push_back(level);
}
return res;
}
107. Binary Tree Level Order Traversal II
Medium
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).
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: [[15,7],[9,20],[3]]
Constraints:
The number of nodes in the tree is in the range [0, 2000].
-1000 <= Node.val <= 1000
[ ]:
// BFS 解答跟上面那題一模一樣只是 return 前加一行 std::reverse(res.begin(), res.end())。LeetCode 上速度前幾名的 BFS 解答都是這樣做的
// 或者把 res.push_back(level) 那行改成 res.insert(0, level)，但理論上會慢一點
103. Binary Tree Zigzag Level Order Traversal
Medium
Given the root of a binary tree, return the zigzag level order traversal of its nodes’ values. (i.e., from left to right, then right to left for the next level and alternate between).
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]
Constraints:
The number of nodes in the tree is in the range [0, 2000].
-100 <= Node.val <= 100
[ ]:
// 作弊的解答同 107 不過在 return 前改 reverse res 裡需要 reverse 的
// 下面是不作弊的方法：每層裡 pop_back 和 pop_front 穿插著用。看 binary tree python（主標題 link）
// 在 pop_back 的一層裡要 push 下一層的 node 就一定要用 push_front 才不會一 push 就被 pop 了
#include <deque>
#include <vector>
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
std::deque<TreeNode*> q;
if (root)
q.push_back(root);
bool from_left = true;
std::vector<std::vector<int>> res;
while (q.size())
{
std::vector<int> level;
int size = q.size();
for (size_t i=0 ; i<size ; i++)
{
if (from_left)
{
TreeNode* node = q.front();
q.pop_front();
level.push_back(node->val);
if (node->left)
q.push_back(node->left);
if (node->right)
q.push_back(node->right);
}else
{
TreeNode* node = q.back();
q.pop_back();
level.push_back(node->val);
if (node->right)
q.push_front(node->right);
if (node->left)
q.push_front(node->left);
}
}
from_left = !from_left;
res.push_back(level);
}
return res;
}
98. Validate Binary Search Tree
Medium
Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.
Example 1:
Input: root = [2,1,3]
Output: true
Constraints:
The number of nodes in the tree is in the range [1, 10^4].
-2^31 <= Node.val <= 2^31 - 1
[ ]:
// 檢查 inorder 結果是否已排序
// 很慢，c++ 大家都用下面的 recursive 寫法
#include <vector>
std::vector<int> inorder_res;
bool isValidBST(TreeNode* root) {
inorder(root);
for (size_t i=0 ; i<inorder_res.size()-1 ; i++)
if (!(inorder_res[i] < inorder_res[i+1]))
return false;
return true;
}
void inorder(TreeNode* root){
if (root){
inorder(root->left);
inorder_res.push_back(root->val);
inorder(root->right);
}
}
[ ]:
// recursive: verify if root is a valid BST taking values in (low, high)
#include <limit> // std::numeric_limits
bool isValidBST(TreeNode* root,
double h=std::numeric_limits<double>::infinity(),
double l=-std::numeric_limits<double>::infinity()) {
if (!root)
return true;
if (root->val >= h || root->val <= l)
return false;
return isValidBST(root->left, root->val, l) && isValidBST(root->right, h, root->val);
}
701. Insert into a Binary Search Tree
Medium
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.
Example 1:
Input: root = [4,2,7,1,3], val = 5
Output: [4,2,7,1,3,5]
Constraints:
The number of nodes in the tree will be in the range [0, 10^4].
-10^8 <= Node.val <= 10^8
All the values Node.val are unique.
-10^8 <= val <= 10^8
It's guaranteed that val does not exist in the original BST.
[ ]:
// naively move to the right place and add a node
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (!root)
return new TreeNode(val);
TreeNode* prev;
TreeNode* cur = root;
while (cur)
{
prev = cur;
if (val > cur->val)
cur = cur->right;
else
cur = cur->left;
}
if (val > prev->val)
prev->right = new TreeNode(val);
else
prev->left = new TreeNode(val);
return root;
}
[ ]:
// clean recursive solution
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (!root)
return new TreeNode(val);
if (root->val < val)
root->right = insertIntoBST(root->right, val);
else
root->left = insertIntoBST(root->left, val);
return root;
}