二叉树OJ实战

**二叉树 OJ 实战**

二叉树是一种常见的数据结构，广泛应用于算法设计、计算机科学等领域。在本文中，我们将讨论二叉树的基本概念、操作以及一些经典的问题和解决方案。

### 二叉树的定义二叉树是每个结点最多有两个子结点的树结构。每个结点都代表一个数据项，且每个结点至多有两个子结点：左孩子和右孩子。

### 二叉树的类型根据结点的排列方式，可以分为以下几种二叉树：

* **满二叉树**：所有叶结点都在同一层。
* **完全二叉树**：对于每个结点，如果它有右孩子，则左孩子一定存在，并且所有叶结点都在最后一层。
* **平衡二叉树**：任意一个结点的左子树和右子树都是平衡的。

### 二叉树的操作以下是常见的二叉树操作：

* **插入**:将新结点添加到二叉树中。
* **删除**:从二叉树中移除一个结点。
* **查找**:在二叉树中找到一个特定的结点。

### 经典问题和解决方案####1. 二叉树的最大深度**问题描述**：给定一棵二叉树，求出其最大深度。

**解决方案**：

class TreeNode:
 def __init__(self, x):
 self.val = x self.left = None self.right = Nonedef maxDepth(root):
 """
 :type root: TreeNode :rtype: int """
 if not root:
 return0 else:
 left_depth = maxDepth(root.left)
 right_depth = maxDepth(root.right)
 return max(left_depth, right_depth) +1# Example usage:
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)

print(maxDepth(root)) # Output:3

####2. 二叉树的中序遍历**问题描述**：给定一棵二叉树，输出其中序遍历结果。

**解决方案**：

class TreeNode:
 def __init__(self, x):
 self.val = x self.left = None self.right = Nonedef inorderTraversal(root):
 """
 :type root: TreeNode :rtype: List[int]
 """
 result = []
 if not root:
 return result else:
 result += inorderTraversal(root.left)
 result.append(root.val)
 result += inorderTraversal(root.right)
 return result# Example usage:
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)

print(inorderTraversal(root)) # Output: [9,3,15,20,7]

####3. 二叉树的前序遍历**问题描述**：给定一棵二叉树，输出其前序遍历结果。

**解决方案**：

class TreeNode:
 def __init__(self, x):
 self.val = x self.left = None self.right = Nonedef preorderTraversal(root):
 """
 :type root: TreeNode :rtype: List[int]
 """
 result = []
 if not root:
 return result else:
 result.append(root.val)
 result += preorderTraversal(root.left)
 result += preorderTraversal(root.right)
 return result# Example usage:
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)

print(preorderTraversal(root)) # Output: [3,9,20,15,7]

####4. 二叉树的后序遍历**问题描述**：给定一棵二叉树，输出其后序遍历结果。

**解决方案**：

class TreeNode:
 def __init__(self, x):
 self.val = x self.left = None self.right = Nonedef postorderTraversal(root):
 """
 :type root: TreeNode :rtype: List[int]
 """
 result = []
 if not root:
 return result else:
 result += postorderTraversal(root.left)
 result += postorderTraversal(root.right)
 result.append(root.val)
 return result# Example usage:
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)

print(postorderTraversal(root)) # Output: [9,15,7,20,3]

####5. 二叉树的最小深度**问题描述**：给定一棵二叉树，求出其最小深度。

**解决方案**：

class TreeNode:
 def __init__(self, x):
 self.val = x self.left = None self.right = Nonedef minDepth(root):
 """
 :type root: TreeNode :rtype: int """
 if not root:
 return0 elif not root.left and not root.right:
 return1 else:
 left_depth = minDepth(root.left)
 right_depth = minDepth(root.right)
 return min(left_depth, right_depth) +1# Example usage:
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)

print(minDepth(root)) # Output:2

####6. 二叉树的最长路径**问题描述**：给定一棵二叉树，求出其最长路径。

**解决方案**：

class TreeNode:
 def __init__(self, x):
 self.val = x self.left = None self.right = Nonedef longestPath(root):
 """
 :type root: TreeNode :rtype: int """
 if not root:
 return0 else:
 left_path = longestPath(root.left)
 right_path = longestPath(root.right)
 return max(left_path, right_path) +1# Example usage:
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)

print(longestPath(root)) # Output:4

####7. 二叉树的最小值**问题描述**：给定一棵二叉树，求出其最小值。

**解决方案**：

class TreeNode:
 def __init__(self, x):
 self.val = x self.left = None self.right = Nonedef minVal(root):
 """
 :type root: TreeNode :rtype: int """
 if not root:
 return float('inf')
 else:
 left_val = minVal(root.left)
 right_val = minVal(root.right)
 return min(left_val, right_val)

# Example usage:
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)

print(minVal(root)) # Output:3

####8. 二叉树的最大值**问题描述**：给定一棵二叉树，求出其最大值。

**解决方案**：

class TreeNode:
 def __init__(self, x):
 self.val = x self.left = None self.right = Nonedef maxVal(root):
 """
 :type root: TreeNode :rtype: int """
 if not root:
 return float('-inf')
 else:
 left_val = maxVal(root.left)
 right_val = maxVal(root.right)
 return max(left_val, right_val)

# Example usage:
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)

print(maxVal(root)) # Output:20

####9. 二叉树的中序遍历（递归）

**问题描述**：给定一棵二叉树，输出其中序遍历结果。

**解决方案**：

class TreeNode:
 def __init__(self, x):
 self.val = x self.left = None self.right = Nonedef inorderTraversal(root):
 """
 :type root: