Binary Tree¶
Table of Contents¶
- 94. Binary Tree Inorder Traversal (Easy)
- 104. Maximum Depth of Binary Tree (Easy)
- 226. Invert Binary Tree (Easy)
- 101. Symmetric Tree (Easy)
- 543. Diameter of Binary Tree (Easy)
- 102. Binary Tree Level Order Traversal (Medium)
- 108. Convert Sorted Array to Binary Search Tree (Easy)
- 98. Validate Binary Search Tree (Medium)
- 230. Kth Smallest Element in a BST (Medium)
- 199. Binary Tree Right Side View (Medium)
- 114. Flatten Binary Tree to Linked List (Medium)
- 105. Construct Binary Tree from Preorder and Inorder Traversal (Medium)
- 437. Path Sum III (Medium)
- 236. Lowest Common Ancestor of a Binary Tree (Medium)
- 124. Binary Tree Maximum Path Sum (Hard)
94. Binary Tree Inorder Traversal¶
from typing import List, Optional
from binarytree import Node as TreeNode
from binarytree import build
# Recursive
def inorderTraversalRecursive(root: TreeNode) -> List[int]:
res = []
def dfs(node):
if not node:
return
dfs(node.left)
res.append(node.val) # <--
dfs(node.right)
dfs(root)
return res
# Iterative
def inorderTraversalIterative(root: Optional[TreeNode]) -> List[int]:
if not root:
return []
stack = []
res = []
cur = root
while cur or stack:
if cur:
stack.append(cur)
cur = cur.left
else:
cur = stack.pop()
res.append(cur.val)
cur = cur.right
return res
tree = build([0, 1, 2, 3, 4, 5, 6])
print(tree)
# __0__
# / \
# 1 2
# / \ / \
# 3 4 5 6
print(inorderTraversalRecursive(tree)) # [3, 1, 4, 0, 5, 2, 6]
print(inorderTraversalIterative(tree)) # [3, 1, 4, 0, 5, 2, 6]
104. Maximum Depth of Binary Tree¶
from collections import deque
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
# Recursive
def maxDepthRecursive(root: Optional[TreeNode]) -> int:
if not root:
return 0
left = maxDepthRecursive(root.left)
right = maxDepthRecursive(root.right)
return 1 + max(left, right)
# DFS
def maxDepthDFS(root: Optional[TreeNode]) -> int:
res = 0
def dfs(node, cnt):
if node is None:
return
cnt += 1
nonlocal res
res = max(res, cnt)
dfs(node.left, cnt)
dfs(node.right, cnt)
dfs(root, 0)
return res
# Iterative
def maxDepthIterative(root: Optional[TreeNode]) -> int:
if not root:
return 0
q = deque([root])
res = 0
while q:
res += 1
n = len(q)
for _ in range(n):
node = q.popleft()
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return res
if __name__ == "__main__":
root = [1, 2, 2, 3, 4, None, None, None, None, 5]
root = build(root)
print(root)
# ____1
# / \
# 2__ 2
# / \
# 3 4
# /
# 5
assert maxDepthRecursive(root) == 4
assert maxDepthDFS(root) == 4
assert maxDepthIterative(root) == 4
226. Invert Binary Tree¶
from typing import Optional
from binarytree import build
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Recursive
def invertTreeRecursive(root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return root
root.left, root.right = root.right, root.left
invertTreeRecursive(root.left)
invertTreeRecursive(root.right)
return root
# Iterative
def invertTreeIterative(root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return root
stack = [root]
while stack:
node = stack.pop()
node.left, node.right = node.right, node.left
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return root
root = build([4, 2, 7, 1, 3, 6, 9])
print(root)
# __4__
# / \
# 2 7
# / \ / \
# 1 3 6 9
invertedRecursive = invertTreeRecursive(root)
print(invertedRecursive)
# __4__
# / \
# 7 2
# / \ / \
# 9 6 3 1
root = build([4, 2, 7, 1, 3, 6, 9])
invertedIterative = invertTreeIterative(root)
print(invertedIterative)
# __4__
# / \
# 7 2
# / \ / \
# 9 6 3 1
101. Symmetric Tree¶
from collections import deque
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
# Recursive
def is_symmetric_recursive(root: Optional[TreeNode]) -> bool:
if not root:
return True
def check(left, right):
if left is right:
return True
if not left or not right or left.val != right.val:
return False
outside = check(left.left, right.right)
inside = check(left.right, right.left)
return outside and inside
return check(root.left, root.right)
# Iterative
def is_symmetric_iterative(root: Optional[TreeNode]) -> bool:
if not root:
return True
q = deque()
q.append(root.left)
q.append(root.right)
while q:
left = q.popleft()
right = q.popleft()
if not left and not right:
continue
if not left or not right or left.val != right.val:
return False
q.append(left.left)
q.append(right.right)
q.append(left.right)
q.append(right.left)
return True
if __name__ == "__main__":
root = [1, 2, 2, 3, 4, 4, 3]
root = build(root)
print(root)
# __1__
# / \
# 2 2
# / \ / \
# 3 4 4 3
assert is_symmetric_recursive(root) is True
assert is_symmetric_iterative(root) is True
543. Diameter of Binary Tree¶
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
# Tree DFS
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
self.diameter = 0
def dfs(node):
if not node:
return 0
left = dfs(node.left)
right = dfs(node.right)
self.diameter = max(self.diameter, left + right)
return 1 + max(left, right)
dfs(root)
return self.diameter
root = build([1, 2, 3, 4, 5])
print(root)
# __1
# / \
# 2 3
# / \
# 4 5
obj = Solution()
print(obj.diameterOfBinaryTree(root)) # 3
#include <algorithm>
#include <iostream>
using namespace std;
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) {}
};
int diameterOfBinaryTree(TreeNode* root) {
int diameter = 0;
auto dfs = [&](auto&& self, TreeNode* node) -> int {
if (!node) return 0;
int left = self(self, node->left);
int right = self(self, node->right);
diameter = max(diameter, left + right);
return 1 + max(left, right);
};
dfs(dfs, root);
return diameter;
}
int main() {
// [1, 2, 3, 4, 5]
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
cout << diameterOfBinaryTree(root) << endl; // 3
return 0;
}
102. Binary Tree Level Order Traversal¶
from collections import deque
from typing import List, Optional
from binarytree import Node as TreeNode
from binarytree import build
def levelOrder(root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
q = deque([root])
res = []
while q:
level = []
size = len(q)
for _ in range(size):
cur = q.popleft()
level.append(cur.val)
if cur.left:
q.append(cur.left)
if cur.right:
q.append(cur.right)
res.append(level)
return res
tree = build([3, 9, 20, None, None, 15, 7])
print(tree)
# 3___
# / \
# 9 _20
# / \
# 15 7
print(levelOrder(tree)) # [[3], [9, 20], [15, 7]]
108. Convert Sorted Array to Binary Search Tree¶
from typing import List, Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def sortedArrayToBST(nums: List[int]) -> Optional[TreeNode]:
if len(nums) == 0:
return None
mid = len(nums) // 2
root = TreeNode(nums[mid])
root.left = sortedArrayToBST(nums[:mid])
root.right = sortedArrayToBST(nums[mid + 1 :])
return root
nums = [-10, -3, 0, 5, 9]
root = sortedArrayToBST(nums)
# 0
# / \
# -3 9
# / /
# -10 5
#include <vector>
using namespace std;
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* sortedArrayToBST(vector<int>& nums) {
if (nums.size() == 0) return nullptr;
int mid = nums.size() / 2;
TreeNode* root = new TreeNode(nums[mid]);
vector<int> left(nums.begin(), nums.begin() + mid);
vector<int> right(nums.begin() + mid + 1, nums.end());
root->left = sortedArrayToBST(left);
root->right = sortedArrayToBST(right);
return root;
}
};
int main() { return 0; }
98. Validate Binary Search Tree¶
from itertools import pairwise
from math import inf
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
def isValidBST1(root: Optional[TreeNode]) -> bool:
inorder = [] # inorder traversal
def dfs(node):
if not node:
return None
dfs(node.left)
inorder.append(node.val)
dfs(node.right)
dfs(root)
for a, b in pairwise(inorder):
if a >= b:
return False
return True
def isValidBST2(root: Optional[TreeNode]) -> bool:
if not root:
return True
pre = -inf
def dfs(node):
if not node:
return True
if not dfs(node.left):
return False
nonlocal pre
if node.val <= pre:
return False
pre = node.val
return dfs(node.right)
return dfs(root)
if __name__ == "__main__":
root = [5, 1, 4, None, None, 3, 6]
root = build(root)
print(root)
# 5__
# / \
# 1 4
# / \
# 3 6
assert not isValidBST1(root) # [1, 5, 3, 4, 6]
assert not isValidBST2(root) # [1, 5, 3, 4, 6]
#include <cassert>
#include <vector>
using namespace std;
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> inorder;
bool check(vector<int> inorder) {
int n = inorder.size();
if (n <= 1) return true;
for (int i = 1; i < n; i++) {
if (inorder[i] <= inorder[i - 1]) return false;
}
return true;
}
public:
bool isValidBST(TreeNode *root) {
auto dfs = [&](auto &&self, TreeNode *node) -> void {
if (!node) return;
self(self, node->left);
inorder.push_back(node->val);
self(self, node->right);
};
dfs(dfs, root);
return check(inorder);
}
};
int main() {
Solution s;
TreeNode *root = new TreeNode(2);
root->left = new TreeNode(1);
root->right = new TreeNode(3);
assert(s.isValidBST(root) == true);
root = new TreeNode(5);
root->left = new TreeNode(1);
root->right = new TreeNode(4);
root->right->left = new TreeNode(3);
root->right->right = new TreeNode(6);
assert(s.isValidBST(root) == false);
root = new TreeNode(5);
root->left = new TreeNode(4);
root->right = new TreeNode(6);
root->right->left = new TreeNode(3);
root->right->right = new TreeNode(7);
assert(s.isValidBST(root) == false);
return 0;
}
230. Kth Smallest Element in a BST¶
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
# Recursive
def kthSmallestRecursive(root: Optional[TreeNode], k: int) -> int:
inorder = []
def dfs(node):
if not node:
return None
dfs(node.left)
inorder.append(node.val)
dfs(node.right)
dfs(root)
return inorder[k - 1]
# Iteratve
def kthSmallestIteratve(root: Optional[TreeNode], k: int) -> int:
stack = []
while True:
while root:
stack.append(root)
root = root.left
root = stack.pop()
k -= 1
if not k:
return root.val
root = root.right
if __name__ == "__main__":
root = build([3, 1, 4, None, 2])
k = 1
assert kthSmallestRecursive(root, k) == 1
assert kthSmallestIteratve(root, k) == 1
199. Binary Tree Right Side View¶
from collections import deque
from typing import List, Optional
from binarytree import Node as TreeNode
from binarytree import build
# Binary Tree BFS
def rightSideViewBFS(root: Optional[TreeNode]) -> List[int]:
if not root:
return []
q = deque([root])
res = []
while q:
n = len(q)
for i in range(n):
node = q.popleft()
if i == n - 1:
res.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return res
# Binary Tree DFS
def rightSideViewDFS(root: Optional[TreeNode]) -> List[int]:
"""后序遍历，先右后左，遇到的第一个节点就是该深度的最右侧节点"""
ans = []
def dfs(node, depth):
if node is None:
return
if depth == len(ans): # 这个深度首次遇到
ans.append(node.val)
dfs(node.right, depth + 1)
dfs(node.left, depth + 1)
dfs(root, 0)
return ans
if __name__ == "__main__":
root = [1, 2, 2, 3, 4, None, 3, None, None, 5]
root = build(root)
print(root)
# ____1
# / \
# 2__ 2
# / \ \
# 3 4 3
# /
# 5
assert rightSideViewBFS(root) == [1, 2, 3, 5]
assert rightSideViewDFS(root) == [1, 2, 3, 5]
114. Flatten Binary Tree to Linked List¶
#include <cassert>
#include <vector>
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) {
if (!root) return;
flatten(root->left);
flatten(root->right);
TreeNode* left = root->left;
TreeNode* right = root->right;
root->left = nullptr;
root->right = left;
TreeNode* curr = root;
while (curr->right) curr = curr->right;
curr->right = right;
}
};
int main() {
Solution sol;
TreeNode* root =
new TreeNode(1, new TreeNode(2, new TreeNode(3), new TreeNode(4)),
new TreeNode(5, nullptr, new TreeNode(6)));
sol.flatten(root);
TreeNode* cur = root;
std::vector<int> expected = {1, 2, 3, 4, 5, 6};
for (int val : expected) {
assert(cur != nullptr && cur->val == val);
cur = cur->right;
}
assert(cur == nullptr); // End of list
return 0;
}
105. Construct Binary Tree from Preorder and Inorder Traversal¶
from typing import List, Optional
from helper import TreeNode
def buildTree(preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
"""
preorder root left right 1 2 3
inorder left root right 4 5 6
"""
if len(preorder) == 0:
return None
root_val = preorder[0] # 1
root = TreeNode(root_val)
separator_idx = inorder.index(root_val) # 5
left_inorder = inorder[:separator_idx] # 4
right_inorder = inorder[separator_idx + 1 :] # 6
left_preorder = preorder[1 : 1 + len(left_inorder)] # 2
right_preorder = preorder[1 + len(left_inorder) :] # 3
root.left = buildTree(left_preorder, left_inorder)
root.right = buildTree(right_preorder, right_inorder)
return root
preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]
root = buildTree(preorder, inorder)
print(root)
# 3
# / \
# 9 20
# / \
# 15 7
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
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> preorder;
unordered_map<int, int> inorderMap;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
this->preorder = preorder;
for (size_t i = 0; i < inorder.size(); i++) {
inorderMap[inorder[i]] = i;
}
return buildSubtree(0, 0, inorder.size() - 1);
}
private:
TreeNode* buildSubtree(int rootIndex, int left, int right) {
if (left > right) return nullptr;
TreeNode* root = new TreeNode(preorder[rootIndex]);
int inorderIndex = inorderMap[preorder[rootIndex]];
root->left = buildSubtree(rootIndex + 1, left, inorderIndex - 1);
root->right = buildSubtree(rootIndex + (inorderIndex - left + 1),
inorderIndex + 1, right);
return root;
}
};
int main() {
vector<int> preorder = {3, 9, 20, 15, 7};
vector<int> inorder = {9, 3, 15, 20, 7};
Solution solution;
TreeNode* root = solution.buildTree(preorder, inorder);
cout << root->val << endl; // 3
cout << root->left->val << endl; // 9
cout << root->right->val << endl; // 20
cout << root->right->left->val << endl; // 15
cout << root->right->right->val << endl; // 7
return 0;
}
437. Path Sum III¶
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
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 pathSum(TreeNode *root, int targetSum) {
int res = 0;
unordered_map<long long, int> cnt{{0, 1}};
auto dfs = [&](auto &&self, TreeNode *node, long long cur) {
if (!node) return;
cur += node->val;
if (cnt.find(cur - targetSum) != cnt.end())
res += cnt[cur - targetSum];
cnt[cur]++;
self(self, node->left, cur);
self(self, node->right, cur);
cnt[cur]--;
};
dfs(dfs, root, 0);
return res;
}
};
int main() {
Solution s;
{
TreeNode *root = new TreeNode(10);
root->left = new TreeNode(5);
root->right = new TreeNode(-3);
root->left->left = new TreeNode(3);
root->left->right = new TreeNode(2);
root->right->right = new TreeNode(11);
root->left->left->left = new TreeNode(3);
root->left->left->right = new TreeNode(-2);
root->left->right->right = new TreeNode(1);
cout << s.pathSum(root, 8) << endl; // 3
}
{
TreeNode *root = new TreeNode(5);
root->left = new TreeNode(4);
root->right = new TreeNode(8);
root->left->left = new TreeNode(11);
root->right->left = new TreeNode(13);
root->right->right = new TreeNode(4);
root->left->left->left = new TreeNode(7);
root->left->left->right = new TreeNode(2);
root->right->right->left = new TreeNode(5);
root->right->right->right = new TreeNode(1);
cout << s.pathSum(root, 22) << endl; // 3
}
return 0;
}
236. Lowest Common Ancestor of a Binary Tree¶
from typing import List, Optional
from binarytree import build
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def lowestCommonAncestor(
root: "TreeNode", p: "TreeNode", q: "TreeNode"
) -> "TreeNode":
if not root or q == root or p == root:
return root
left = lowestCommonAncestor(root.left, p, q)
right = lowestCommonAncestor(root.right, p, q)
if left and right:
return root
return left or right
root = build([3, 5, 1, 6, 2, 0, 8, None, None, 7, 4])
print(root)
# ______3__
# / \
# 5__ 1
# / \ / \
# 6 2 0 8
# / \
# 7 4
p = root.left # 5
q = root.right # 1
print(lowestCommonAncestor(root, p, q)) # 3
# ______3__
# / \
# 5__ 1
# / \ / \
# 6 2 0 8
# / \
# 7 4
r = root.left.right.right # 4
print(lowestCommonAncestor(root, p, r)) # 5
# 5__
# / \
# 6 2
# / \
# 7 4
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
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* 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;
}
};
int main() { return 0; }
124. Binary Tree Maximum Path Sum¶
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
def maxPathSum(root: Optional[TreeNode]) -> int:
res = float("-inf")
def dfs(node):
if not node:
return 0
leftMax = max(dfs(node.left), 0)
rightMax = max(dfs(node.right), 0)
cur = node.val + leftMax + rightMax
nonlocal res
res = max(res, cur)
return node.val + max(leftMax, rightMax)
dfs(root)
return res
root = build([-10, 9, 20, None, None, 15, 7])
print(root)
# -10___
# / \
# 9 _20
# / \
# 15 7
print(maxPathSum(root)) # 42