难度: Medium
Submission
运行时间: 118 ms
内存: 20.7 MB
# 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 heightOfTree(self, root: Optional[TreeNode]) -> int:
queue = [root]
level = -1
while queue:
level += 1
queue_ = []
for node in queue:
if node.left and node.left.right != node:
queue_.append(node.left)
if node.right and node.right.left != node:
queue_.append(node.right)
queue = queue_
return level
Explain
这个题解使用了广度优先搜索（BFS）的方法来遍历二叉树，并计算树的高度。队列 `queue` 用于存放每一层的节点。对每一层的节点进行迭代处理，若节点具有子节点，则将子节点加入到下一层的队列 `queue_` 中。这里有一个特殊的条件检查，对于左子节点，只有当左子节点的右子节点不是当前节点时，才将其加入队列；对于右子节点，只有当右子节点的左子节点不是当前节点时，才将其加入队列。这可能是为了避免某种特殊结构的循环引用。每迭代完一层，层数 `level` 自增1。
时间复杂度: O(n)
空间复杂度: O(n)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# this.val = val
# this.left = left
# this.right = right
class Solution:
def heightOfTree(self, root: Optional[TreeNode]) -> int:
if not root: # 如果根节点为空，则树的高度为0
return 0
queue = [root] # 初始化队列，开始时只包含根节点
level = -1 # 初始化层级计数，开始于-1因为根节点之前没有层级
while queue: # 只要队列不为空，继续遍历
level += 1 # 进入新的一层
queue_ = [] # 准备下一层的队列
for node in queue: # 遍历当前层的每个节点
if node.left and node.left.right != node: # 检查左子节点的特殊条件
queue_.append(node.left) # 将符合条件的左子节点加入下一层队列
if node.right and node.right.left != node: # 检查右子节点的特殊条件
queue_.append(node.right) # 将符合条件的右子节点加入下一层队列
queue = queue_ # 更新队列为下一层的节点
return level # 返回最后计算的层级，即树的高度
Explore
在二叉树的上下文中，循环引用指的是通过子节点的链接可以回到先前的某个祖先节点，形成一个闭环。例如，一个节点A的左子节点B的右子节点是A，这就形成了A->B->A的循环。这种结构会影响树的遍历，因为在广度优先搜索或深度优先搜索中，算法可能会重复访问相同的节点，导致无限循环。为了防止这种情况，在题解中通过特殊条件检查来避免将形成循环的节点加入到遍历队列中。
特殊条件检查的目的是为了防止在遍历过程中发生循环引用，从而避免无限循环。对于左子节点，检查条件是确保左子节点的右子节点不是当前节点；对于右子节点，则确保右子节点的左子节点不是当前节点。这些检查有效地阻止了简单的二级循环引用。然而，对于更复杂的循环结构，例如跨越多个节点的循环，这些条件可能不足以完全避免所有可能的循环引用。为了彻底解决这个问题，可以考虑使用一个标记或访问历史记录来追踪已经访问过的节点。
将层级 `level` 初始化为-1的主要原因是为了在进入第一层（包含根节点的层）时通过层级增加操作将其设置为0。这种设计使得每次开始处理新的一层节点时，层级 `level` 自动递增，从而在循环结束时直接反映树的高度。如果初始化为0，那么最后得到的层数会比实际树的高度多1，因为根节点本身代表第0层，而不是第1层。