Recursion: depth first search

The maximum depth of a binary tree

The problem of binary tree usually gives priority to recursion , We want to ask for the depth of a tree , When we know the depth of the left subtree and the right subtree , that root The depth of the node is the maximum value of the left and right subtrees plus 1
$$depth(root)=max(depth(root.left),depth(root.right))+1$$
Obviously, this is also a recursive formula , So you can use recursion directly

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        def dfs(root):
            if not root: # base case
                return 0
            l = dfs(root.left) #  First find the depth of the left subtree 
            r = dfs(root.right) #  Then find the depth of the right subtree 
            return max(l,r)+1 #  The lion , And then add root The node is +1
        return dfs(root)

Minimum depth of binary tree

At first, I felt that the minimum depth was the same as the maximum depth , But find it written directly min There is a problem .

The most important question is , The minimum depth is from the leaf node , therefore base case There are two kinds of , One is head==None, The other way is head.right is None and head.left is None. It must start from the leaf node .

Wrong writing , You can see a node ,a The left subtree depth of the node is 0, The depth of the right subtree is 2, Then according to the recursive formula of this error, we can get a The minimum depth of the node is min(0,2)=0, But obviously ,a Node is not a leaf node , So we can't find the minimum depth . But the maximum depth will not have such a problem .

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0
        return min(self.minDepth(root.right),self.minDepth(root.left))+1

To write correctly, you need to consider that a subtree is None The situation of , At this time, we need to recurse the subtree on the other side as the minimum depth .

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0
        elif root.left is None and root.right is None:
            return 1
        elif root.left is None:
            return self.minDepth(root.right)+1
        elif root.right is None:
            return  self.minDepth(root.left) + 1
        else:
            return min(self.minDepth(root.right),self.minDepth(root.left))+1

Balanced binary trees

Given a binary tree , Determine if it's a highly balanced binary tree .
In this question , A height balanced binary tree is defined as ：
Every node of a binary tree The absolute value of the height difference between the left and right subtrees is not more than 1

The essence of this problem is to solve the depth of the tree , It is only required that the depth difference between the left and right subtrees should not exceed 1, If it exceeds one, it will return directly False. The same understanding , We want to know root Nodes are balanced , Then we need to calculate the height of the left and right subtrees , After calculating the height , We also need to judge whether the left and right subtrees are also balanced binary trees , If one is not , that root Certainly not

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        def dfs(root):
            if not root:
                return 0,True
            l,lf = dfs(root.left)
            r,rf = dfs(root.right)

            if abs(l-r) <= 1 and lf and rf:
                return max(l,r)+1,True
            else:
                return max(l,r)+1,False
        
        _,f = dfs(root)
        return f

The number of nodes in a complete binary tree

Counting numbers is also very simple , We count the number of left subtrees and then add the number of right subtrees , Then add the root node to get the total number of nodes .

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
    def countNodes(self, root: TreeNode) -> int:
        if root is None:
            return 0
        return self.countNodes(root.left) + self.countNodes(root.right) + 1