难度: Easy
Submission
运行时间: 36 ms
内存: 16.4 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 getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:
ans, stk = [], []
while root or stk:
if root:
stk.append(root)
if root.left and not root.right:
ans.append(root.left.val)
if not root.left and root.right:
ans.append(root.right.val)
root = root.left
else:
root = stk.pop()
root = root.right
return ans
Explain
该题解采用了迭代方式进行二叉树的遍历，主要使用了栈（stack）来模拟递归过程，从而对二叉树进行深度优先搜索（DFS）。在遍历时，每当访问一个节点，检查其是否具有独生子节点（即只有左孩子或只有右孩子），若是，则将该子节点的值加入结果列表。通过先进后出的栈结构，先将当前节点推入栈中，然后移动到左子节点，直到左侧无子节点，再从栈中取出节点转向右子节点。这种方式确保了每个节点都被访问一次。
时间复杂度: O(n)
空间复杂度: O(n)
# 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 getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:
ans, stk = [], [] # 初始化结果列表和栈
while root or stk: # 当树不为空或栈不为空时进行循环
if root:
stk.append(root) # 将当前节点入栈
if root.left and not root.right:
ans.append(root.left.val) # 如果只有左子节点，添加到结果列表
if not root.left and root.right:
ans.append(root.right.val) # 如果只有右子节点，添加到结果列表
root = root.left # 移至左子节点
else:
root = stk.pop() # 从栈中取出节点并转向右子节点
root = root.right
return ans
Explore
在二叉树的深度优先搜索（DFS）中，使用栈是为了模拟递归的行为，即后进先出的特性。递归的执行本质上是在调用栈上操作，每次处理最后进入的元素。如果使用队列（先进先出的特性），则会变成宽度优先搜索（BFS），这种搜索方式会按层级遍历树，而不是深入到每个分支的末端，这与深度优先搜索的目标不符。
如果一个节点既有左子节点又有右子节点，这两个子节点都不会被考虑为独生节点。根据题目的定义，独生节点是指一个节点只有一个子节点（要么只有左子节点，要么只有右子节点）。因此，如果一个节点的两个子节点都存在，这两个子节点均不满足独生节点的条件。
在从栈中弹出节点并转向右子节点的过程中，不需要再次检查右子节点是否独生。这是因为右子节点的独立性已经在其父节点被第一次访问时判断过了。在算法中，每个节点在第一次遇到时（未从栈中弹出前）就已经完成了对其子节点的独生状态检查。因此，不必在转向右子节点时重复这一检查。
在该题解中，树中节点值为null的情况通常指的是某个节点不存在左子节点或右子节点。这在代码中通过检查 `root.left` 和 `root.right` 是否为 `None` 来处理。如果 `root.left` 为 `None`，则说明没有左子节点；如果 `root.right` 为 `None`，则说明没有右子节点。这种处理方式确保了在添加独生节点值至结果列表时，不会因为尝试访问不存在的子节点的值而导致错误。