0104._maximum_depth_of_binary_tree.md

Navigation

• Navigation
• Links:
• Tags
• Solution 1 DFS（深度优先搜索），递归
• Solution 2 DFS，迭代
• Solution 3 BFS

Links:

1. https://leetcode.com/problems/maximum-depth-of-binary-tree/
2. https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

Tags

1. 树
2. 深度优先搜索

Solution 1 DFS（深度优先搜索），递归

class Solution:
    def maxDepth(self, root):
        if not root:
            return 0

        left_height = self.maxDepth(root.left)
        right_height = self.maxDepth(root.right)
        return max(left_height, right_height) + 1

---

class Solution:
    def maxDepth(self, root):
        return 1 + max(map(self.maxDepth, (root.left, root.right))) if root else 0

---

Go

func max(a, b int) int {
	if a > b {
		return a
	}

	return b
}

func maxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}

	return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
}

Solution 2 DFS，迭代

DFS借助栈实现。Solution 1是系统栈，Solution 2是自己定义的栈。 每次搜索都更新最大深度。

class Solution:
    def maxDepth(self, root):

        stack = []
        if root:
            stack.append((1, root))
        
        depth = 0
        while stack:
            current_depth, root = stack.pop()
            if root:
                depth = max(depth, current_depth)
                # 以下两行顺序可以互换。
                stack.append((current_depth + 1, root.right))
                stack.append((current_depth + 1, root.left))
        
        return depth

---

class Solution:
    def maxDepth(self, root):

        stack = []
        if root:
            stack.append((1, root))
        
        depth = 0
        while stack:
            current_depth, root = stack.pop()
            
            depth = max(depth, current_depth)
                
            if root.right:
                stack.append((current_depth + 1, root.right))
            if root.left:
                stack.append((current_depth + 1, root.left))
        
        return depth

Solution 3 BFS

BFS借助队列实现。

from collections import deque

class Solution:
    def maxDepth(self, root):

        deq = deque()
        if root:
            deq.append((1, root))
        
        depth = 0
        while deq:
            current_depth, root = deq.popleft()
            
            if root:
                depth = current_depth
                # 以下两行顺序可以互换。
                deq.append((current_depth + 1, root.right))
                deq.append((current_depth + 1, root.left))
        
        return depth

---

from collections import deque

class Solution:
    def maxDepth(self, root):

        deq = deque()
        if root:
            deq.append((1, root))
        
        depth = 0
        while deq:
            current_depth, root = deq.popleft()
            
            depth = current_depth
            
            if root.right:
                deq.append((current_depth + 1, root.right))
            if root.left:
                deq.append((current_depth + 1, root.left))
        
        return depth

---

Go

func maxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}

	q := make([]*TreeNode, 0)
	q = append(q, root)
	depth := 0

	for len(q) > 0 {
		length := len(q)
		for length > 0 {
			node := q[0]
			q = q[1:]

			if node.Left != nil {
				q = append(q, node.Left)
			}

			if node.Right != nil {
				q = append(q, node.Right)
			}
			length--
		}
		depth++
	}

	return depth
}