Sword finger offer 55 - I. depth of binary tree

The finger of the sword Offer 55 - I. The depth of the binary tree https://leetcode.cn/problems/er-cha-shu-de-shen-du-lcof/

The traversal methods of trees are generally divided into two categories ： Depth-first search （DFS）、 Breadth first search （BFS）;

common DFS ： The first sequence traversal 、 In the sequence traversal 、 After the sequence traversal ;
common BFS ： Sequence traversal （ That is, traverse by layer ）.

Depth first search of trees often uses recursive or Stack Realization , This article uses recursion to realize .

Method 1 ： The first sequence traversal (DFS)

Termination conditions ： Compare the final results when leaf nodes res And the depth of this road

Recursive parameter ： Current node node, Depth of current road k

Recursive work ： Traverse the left and right child nodes of the current node

class Solution:
    def maxDepth(self, root):
        def dfs(node,k):
            if not node:
                if self.res<k:
                    self.res=k
                    return
                else:
                    return
            k+=1
            dfs(node.left,k)
            dfs(node.right,k)
        self.res=float("-inf")
        dfs(root,0)
        return self.res

To find the depth of the tree, you need to traverse all nodes of the tree , The following will introduce based on After the sequence traversal （DFS） and Sequence traversal （BFS） There are two solutions to this problem .
Method 2 ： After the sequence traversal （ Left and right ）（DFS）
Key points ： The depth of this tree and its left （ Right ） The relationship between the depth of the subtree . obviously , The depth of this tree be equal to The depth of the left subtree And Depth of right subtree Medium Maximum +1.
Termination conditions ： When root​ It's empty , Indicates that the leaf node... Has been crossed , Therefore return depth 0 .
Recursive work ： In essence, it is a post order traversal of the tree .
Computing node root​ Of The depth of the left subtree , That is to call maxDepth(root.left);
Computing node root​ Of Depth of right subtree , That is to call maxDepth(root.right);
Return value ： return The depth of this tree , namely max(maxDepth(root.left), maxDepth(root.right)) + 1.

class Solution:
    def maxDepth(self, root):
        def dfs(node):
            if not node:return 0
            return max(dfs(node.left),dfs(node.right))+1
        return dfs(root)

Method 3 ： Sequence traversal （BFS）
Sequence traversal of trees / Breadth first search often uses queue Realization .
Key points ： Every layer , Then the counter +1 , Until the traversal is complete , Then you can get the depth of the tree .
Algorithm analysis ：
Special case handling ： When root​ It's empty , Go straight back to depth 0 .
initialization ： queue queue （ Add the root node root ）, Counter res = 0.
Loop traversal ： When queue Jump out when empty .
Initialize an empty list tmp , It is used to temporarily store the nodes of the next layer ;
Traverse the queue ： Traverse queue The nodes in node , And add its left child node and right child node tmp;
Update queue ： perform queue = tmp , Assign the next level node to queue;
Count the number of floors ： perform res += 1 , Represents the number of layers plus 1;
Return value ： return res that will do .

Implement queue with list

class Solution:
    def maxDepth(self, root):
       if not root:return 0
       queue=[root]
       res=0
       while queue:
           tmp = []
           for node in queue:
               if node.left:
                   tmp.append(node.left)
               if node.right:
                   tmp.append(node.right)
           queue=tmp
           res+=1
       return res

Use a two-way queue  

import collections
class Solution:
    def maxDepth(self, root):
       if not root:return 0# Note that the depth of the tree is empty 
       queue=collections.deque()
       queue.append(root)
       res=0
       while queue:
           tmp=collections.deque()
           while queue:
               node=queue.popleft()
               if node.left:
                   tmp.append(node.left)
               if node.right:
                   tmp.append(node.right)
           queue=tmp
           res+=1
       return res