Trees¶
Table of Contents¶
- 226. Invert Binary Tree (Easy)
- 104. Maximum Depth of Binary Tree (Easy)
- 543. Diameter of Binary Tree (Easy)
- 110. Balanced Binary Tree (Easy)
- 100. Same Tree (Easy)
- 572. Subtree of Another Tree (Easy)
- 235. Lowest Common Ancestor of a Binary Search Tree (Medium)
- 102. Binary Tree Level Order Traversal (Medium)
- 199. Binary Tree Right Side View (Medium)
- 1448. Count Good Nodes in Binary Tree (Medium)
- 98. Validate Binary Search Tree (Medium)
- 230. Kth Smallest Element in a BST (Medium)
- 105. Construct Binary Tree from Preorder and Inorder Traversal (Medium)
- 124. Binary Tree Maximum Path Sum (Hard)
- 297. Serialize and Deserialize Binary Tree (Hard)
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
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
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;
}
110. Balanced 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 isBalanced(root: Optional[TreeNode]) -> bool:
def getHeight(node):
if not node:
return 0
# post order
leftHeight = getHeight(node.left)
rightHeight = getHeight(node.right)
if leftHeight == -1 or rightHeight == -1:
return -1
if abs(leftHeight - rightHeight) > 1:
return -1
else:
return 1 + max(leftHeight, rightHeight)
if getHeight(root) != -1:
return True
else:
return False
root = [3, 9, 20, None, None, 15, 7]
root = build(root)
print(root)
# 3___
# / \
# 9 _20
# / \
# 15 7
print(isBalanced(root)) # True
100. Same Tree¶
from collections import deque
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
# 1. Recursive
def isSameTreeRecursive(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if not p and not q:
return True
elif not p or not q:
return False
elif p.val != q.val:
return False
return isSameTreeRecursive(p.left, q.left) and isSameTreeRecursive(
p.right, q.right
)
# 2. Iterative with queue
def isSameTreeIterativeQueue(
p: Optional[TreeNode], q: Optional[TreeNode]
) -> bool:
queue = deque([(p, q)])
while queue:
p, q = queue.popleft()
if not p and not q:
continue
if not p or not q:
return False
if p.val != q.val:
return False
queue.append((p.left, q.left))
queue.append((p.right, q.right))
return True
# 3. Iterative with stack
def isSameTreeIterativeStack(
p: Optional[TreeNode], q: Optional[TreeNode]
) -> bool:
stack = [(p, q)]
while stack:
n1, n2 = stack.pop()
if not n1 and not n2:
continue
if not n1 or not n2:
return False
if n1.val != n2.val:
return False
stack.append((n1.left, n2.left))
stack.append((n1.right, n2.right))
return True
if __name__ == "__main__":
p1 = build([1, 2, 3])
q1 = build([1, 2, 3])
p2 = build([1, 2])
q2 = build([1, None, 2])
assert isSameTreeRecursive(p1, q1) is True
assert isSameTreeRecursive(p2, q2) is False
assert isSameTreeIterativeQueue(p1, q1) is True
assert isSameTreeIterativeQueue(p2, q2) is False
assert isSameTreeIterativeStack(p1, q1) is True
assert isSameTreeIterativeStack(p2, q2) is False
572. Subtree of Another Tree¶
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
# DFS - Tree
def isSubtree(root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
def isSameTree(p, q):
if not p and not q:
return True
if not p or not q:
return False
if p.val != q.val:
return False
return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)
if not root:
return False
return (
isSameTree(root, subRoot)
or isSubtree(root.left, subRoot)
or isSubtree(root.right, subRoot)
)
# |------------|---------|----------|
# | Approach | Time | Space |
# |------------|---------|----------|
# | DFS | O(n * m)| O(n) |
# |------------|---------|----------|
root = build([3, 4, 5, 1, 2, None, None, None, None, 0])
subRoot = build([4, 1, 2])
print(root)
# ____3
# / \
# 4__ 5
# / \
# 1 2
# /
# 0
print(subRoot)
# 4
# / \
# 1 2
print(isSubtree(root, subRoot)) # False
235. Lowest Common Ancestor of a Binary Search Tree¶
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":
while root:
if root.val > p.val and root.val > q.val:
root = root.left
elif root.val < p.val and root.val < q.val:
root = root.right
else:
return root
root = [6, 2, 8, 0, 4, 7, 9, None, None, 3, 5]
root = build(root)
p = root.left
q = root.right
print(root)
# ______6__
# / \
# 2__ 8
# / \ / \
# 0 4 7 9
# / \
# 3 5
print(lowestCommonAncestor(root, p, q))
# ______6__
# / \
# 2__ 8
# / \ / \
# 0 4 7 9
# / \
# 3 5
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]]
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]
1448. Count Good Nodes in Binary Tree¶
from typing import List
from binarytree import Node as TreeNode
from binarytree import build
# Tree
def goodNodes(root: TreeNode) -> int:
def dfs(node, max_val):
if not node:
return 0
good = 1 if node.val >= max_val else 0
max_val = max(max_val, node.val)
good += dfs(node.left, max_val)
good += dfs(node.right, max_val)
return good
return dfs(root, root.val)
root = build([3, 1, 4, 3, None, 1, 5])
print(root)
# 3__
# / \
# 1 4
# / / \
# 3 1 5
print(goodNodes(root)) # 4
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
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;
}
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
297. Serialize and Deserialize Binary Tree¶
from collections import deque
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
# BFS
class BFS:
def serialize(self, root: Optional[TreeNode]) -> str:
if not root:
return ""
res = []
q = deque([root])
while q:
node = q.popleft()
if node:
res.append(str(node.val))
q.append(node.left)
q.append(node.right)
else:
res.append("null")
return ",".join(res)
def deserialize(self, data: str) -> Optional[TreeNode]:
if not data:
return None
nodes = data.split(",")
root = TreeNode(int(nodes[0]))
q = deque([root])
index = 1
while q:
node = q.popleft()
if nodes[index] != "null":
node.left = TreeNode(int(nodes[index]))
q.append(node.left)
index += 1
if nodes[index] != "null":
node.right = TreeNode(int(nodes[index]))
q.append(node.right)
index += 1
return root
# DFS
class DFS:
def serialize(self, root: Optional[TreeNode]) -> str:
def dfs(node):
if not node:
return ["null"]
return [str(node.val)] + dfs(node.left) + dfs(node.right)
return ",".join(dfs(root))
def deserialize(self, data: str) -> Optional[TreeNode]:
nodes = data.split(",")
self.index = 0
def dfs():
if nodes[self.index] == "null":
self.index += 1
return None
node = TreeNode(int(nodes[self.index]))
self.index += 1
node.left = dfs()
node.right = dfs()
return node
root = dfs()
return root
root = build([1, 2, 3, None, None, 4, 5])
print(root)
# 1__
# / \
# 2 3
# / \
# 4 5
bfs = BFS()
data1 = bfs.serialize(root)
print(data1) # "1,2,3,null,null,4,5,null,null,null,null"
root1 = bfs.deserialize(data1)
print(root1)
# 1__
# / \
# 2 3
# / \
# 4 5
dfs = DFS()
data2 = dfs.serialize(root)
print(data2) # "1,2,null,null,3,4,null,null,5,null,null"
root2 = dfs.deserialize(data2)
print(root2)
# 1__
# / \
# 2 3
# / \
# 4 5