单选题 适中
#16957

下列代码实现了树的深度优先遍历,则横线处应填入( )。 class TreeNode : def __init__ ( self , x ) : self .…

下列代码实现了树的深度优先遍历,则横线处应填入( )。

class TreeNode: 
    def __init__(self, x): 
        self.val = x 
        self.left = None 
        self.right = None 
def dfs1(root): 
    if not root: 
        return 
    temp = [] 
    temp.append(root) 
    while temp: 
        node = temp[-1] 
        temp.pop() 
        print(node.val, end=" ") 
        if node.right: 
            temp.append(node.right) 
        if node.left: 
            temp.append(node.left) 
def dfs2(root): 
    if not root: 
        return 
    st = [] 
    st.append(root) 
    while st: 
        node = st[-1] 
        st.pop() 
        print(node.val, end=" ") 
        if node.right: 
            st.append(node.right) 
        ——————————————————


未登录也能判分,登录后才会记录
答案与解析
正确答案:A
解析
分析代码逻辑,观察遍历过程中栈的使用方式。dfs1函数中先将右子节点压栈,再将左子节点压栈,导致左子节点先被弹出处理,实现的是根-左-右的访问顺序。dfs2函数结构与dfs1一致,已存在对右子节点的判断和压栈操作。为保持相同的遍历顺序,需在右子节点之后处理左子节点。栈为后进先出结构,因此后续入栈的左子节点将在下一轮循环中优先被访问。需补全对左子节点的条件判断及入栈操作,以维持与dfs1一致的处理流程。