Leetcode Day 12 - Binary Tree: Tree Structure and Depth
Involves manipulating binary tree structures, such as inverting a binary tree and determining symmetry. Also covers finding the maximum and minimum depth of a tree.
Binary Tree
| Diff | Problem | Python | Java |
|---|---|---|---|
 | 226 Invert Binary Tree | ✅ | |
| 101 Symmetric Tree | ✅ | |
| 104 Maximum Depth of Binary Tree | ✅ | |
| 111 Minimum Depth of Binary Tree | ✅ |
Invert Binary Tree
Given the root of a binary tree, invert the tree, and return its root.
1
2
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
Example 2
1
2
Input: root = [2,1,3]
Output: [2,3,1]
Example 3
1
2
Input: root = []
Output: []
Solution
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
def invertTree(self, root):
if root is None:
return
temp = root.left
root.left = root.right
root.right = temp
self.invertTree(root.left)
self.invertTree(root.right)
return root
Similar Questions
| Diff | Similar Questions | Python | Java |
|---|---|---|---|
 | 2415 Reverse Odd Levels of Binary Tree3 | ✅ |
Symmetric Tree
Link to Leetcode question[^rnnfeol]
Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
Example 1
1
2
Input: root = [1,2,2,3,4,4,3]
Output: true
Example 2
1
2
Input: root = [1,2,2,null,3,null,3]
Output: false
Solution
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
def compare(left, right):
if left is None and right is None:
return True
elif left is None and right is not None:
return False
elif right is None and left is not None:
return False
elif left.val != right.val:
return False
outside = compare(left.left, right.right)
inside = compare(left.right, right.left)
return outside and inside
return compare(root.left, root.right)
Maximum Depth of Binary Tree
Example 1
1
2
Input: root = [3,9,20,null,null,15,7]
Output: 3
Example 2
1
2
Input: root = [1,null,2]
Output: 2
Solution
Python
1
2
3
4
5
6
7
8
9
class Solution(object):
def maxDepth(self, root):
def depth_of(node, depth):
if node is None:
return depth
return 1 + max(depth_of(node.left, depth), depth_of(node.right, depth))
return depth_of(root, 0)
Minimum Depth of Binary Tree
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.
Example 1
1
2
Input: root = [3,9,20,null,null,15,7]
Output: 2
Example 2
1
2
Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5
Solution
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
def minDepth(self, root):
if root is None:
return 0
depth = 1
if root.left is not None and root.right is not None:
depth += min(self.minDepth(root.left), self.minDepth(root.right))
elif root.left is not None:
depth += self.minDepth(root.left)
elif root.right is not None:
depth += self.minDepth(root.right)
return depth
Reference
Leetcode-226 Invert Binary Tree: https://leetcode.com/problems/invert-binary-tree/description/. ↩︎
代码随想录-翻转二叉树: https://programmercarl.com/0226.翻转二叉树.html. ↩︎
Leetcode-2415 Reverse Odd Levels of Binary Tree: https://leetcode.com/problems/reverse-odd-levels-of-binary-tree/. ↩︎
代码随想录-对称二叉树: https://programmercarl.com/0101.对称二叉树.html#算法公开课. ↩︎
Leetcode-104 Maximum Depth of Binary Tree: https://leetcode.com/problems/maximum-depth-of-binary-tree/description/. ↩︎
代码随想录-二叉树的层序遍历 II: https://programmercarl.com/0102.二叉树的层序遍历.html. ↩︎ ↩︎2
Leetcode-111 Minimum Depth of Binary Tree: https://leetcode.com/problems/minimum-depth-of-binary-tree/description/. ↩︎