Leetcode Day 12 - Binary Tree: Tree Structure and Depth

Binary Tree

Link to note about 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

Link to Leetcode question¹

Given the root of a binary tree, invert the tree, and return its root.

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Example 2

Input: root = [2,1,3]
Output: [2,3,1]

Example 3

Input: root = []
Output: []

Solution

A detailed explaination of solution can be found here².

Python

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

Input: root = [1,2,2,3,4,4,3]
Output: true

Example 2

Input: root = [1,2,2,null,3,null,3]
Output: false

Solution

A detailed explaination of solution can be found here⁴.

Python

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

Link to Leetcode question⁵

Example 1

Input: root = [3,9,20,null,null,15,7]
Output: 3

Example 2

Input: root = [1,null,2]
Output: 2

Solution

A detailed explaination of solution can be found here⁶.

Python

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

Link to Leetcode question⁷

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

Input: root = [3,9,20,null,null,15,7]
Output: 2

Example 2

Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5

Solution

A detailed explaination of solution can be found here⁶.

Python

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

1. Leetcode-226 Invert Binary Tree: https://leetcode.com/problems/invert-binary-tree/description/. ↩︎

2. 代码随想录-翻转二叉树: https://programmercarl.com/0226.翻转二叉树.html. ↩︎

3. Leetcode-2415 Reverse Odd Levels of Binary Tree: https://leetcode.com/problems/reverse-odd-levels-of-binary-tree/. ↩︎

4. 代码随想录-对称二叉树: https://programmercarl.com/0101.对称二叉树.html#算法公开课. ↩︎

5. Leetcode-104 Maximum Depth of Binary Tree: https://leetcode.com/problems/maximum-depth-of-binary-tree/description/. ↩︎

6. 代码随想录-二叉树的层序遍历 II: https://programmercarl.com/0102.二叉树的层序遍历.html. ↩︎ ↩︎²

7. Leetcode-111 Minimum Depth of Binary Tree: https://leetcode.com/problems/minimum-depth-of-binary-tree/description/. ↩︎