Binary Tree¶
Table of Contents¶
- 226. Invert Binary Tree (Easy)
- 110. Balanced Binary Tree (Easy)
- 543. Diameter of Binary Tree (Easy)
- 104. Maximum Depth of Binary Tree (Easy)
- 102. Binary Tree Level Order Traversal (Medium)
- 236. Lowest Common Ancestor of a Binary Tree (Medium)
- 199. Binary Tree Right Side View (Medium)
- 105. Construct Binary Tree from Preorder and Inorder Traversal (Medium)
- 297. Serialize and Deserialize Binary Tree (Hard)
226. Invert Binary Tree¶
-
LeetCode | LeetCode CH (Easy)
-
Tags: tree, depth first search, breadth first search, binary tree
226. Invert Binary Tree - Python Solution
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
110. Balanced Binary Tree¶
-
LeetCode | LeetCode CH (Easy)
-
Tags: tree, depth first search, binary tree
110. Balanced Binary Tree - Python Solution
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
543. Diameter of Binary Tree¶
-
LeetCode | LeetCode CH (Easy)
-
Tags: tree, depth first search, binary tree
543. Diameter of Binary Tree - Python Solution
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
543. Diameter of Binary Tree - C++ Solution
#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;
}
104. Maximum Depth of Binary Tree¶
-
LeetCode | LeetCode CH (Easy)
-
Tags: tree, depth first search, breadth first search, binary tree
104. Maximum Depth of Binary Tree - Python Solution
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
root = [1, 2, 2, 3, 4, None, None, None, None, 5]
root = build(root)
print(root)
# ____1
# / \
# 2__ 2
# / \
# 3 4
# /
# 5
print(maxDepthRecursive(root)) # 4
print(maxDepthIterative(root)) # 4
print(maxDepthDFS(root)) # 4
102. Binary Tree Level Order Traversal¶
-
LeetCode | LeetCode CH (Medium)
-
Tags: tree, breadth first search, binary tree
102. Binary Tree Level Order Traversal - Python Solution
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]]
236. Lowest Common Ancestor of a Binary Tree¶
-
LeetCode | LeetCode CH (Medium)
-
Tags: tree, depth first search, binary tree
236. Lowest Common Ancestor of a Binary Tree - Python Solution
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
236. Lowest Common Ancestor of a Binary Tree - C++ Solution
#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; }
199. Binary Tree Right Side View¶
-
LeetCode | LeetCode CH (Medium)
-
Tags: tree, depth first search, breadth first search, binary tree
199. Binary Tree Right Side View - Python Solution
from collections import deque
from typing import List, Optional
from binarytree import Node as TreeNode
from binarytree import build
# Binary Tree
def rightSideView(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
root = [1, 2, 2, 3, 4, None, 3, None, None, 5]
root = build(root)
print(root)
# ____1
# / \
# 2__ 2
# / \ \
# 3 4 3
# /
# 5
print(rightSideView(root)) # [1, 2, 3, 5]
105. Construct Binary Tree from Preorder and Inorder Traversal¶
-
LeetCode | LeetCode CH (Medium)
-
Tags: array, hash table, divide and conquer, tree, binary tree
105. Construct Binary Tree from Preorder and Inorder Traversal - Python Solution
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
105. Construct Binary Tree from Preorder and Inorder Traversal - C++ Solution
#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;
}
297. Serialize and Deserialize Binary Tree¶
-
LeetCode | LeetCode CH (Hard)
-
Tags: string, tree, depth first search, breadth first search, design, binary tree
297. Serialize and Deserialize Binary Tree - Python Solution
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