使用中序遍历验证相同二叉树时测试用例失败,求解决方案
解决LeetCode 100题《相同的树》中序遍历解法失败问题
我正在做LeetCode第100题《相同的树》,题目要求:给定两棵二叉树的根节点p和q,编写函数判断它们是否相同。只有当两棵树结构完全一致,且所有对应节点的值都相同时,才判定为相同。
我用DFS实现了前序和后序遍历的解法,都通过了所有测试用例,但改用中序遍历时,在60个测试用例里的第58个失败了,怎么都修不好。附上我的代码和这个测试用例的两棵树结构图片,求帮忙找出问题所在。
# 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 isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool: def inorder(root,q): if root: inorder(root.left,q) q.append(root.val) inorder(root.right,q) else: q.append(None) return q q1 = inorder(p,[]) q2 = inorder(q,[]) print(q1) print(q2) return q1==q2
测试用例树结构:

内容的提问来源于stack exchange,提问作者Umme Habiba
相关产品推荐
相关产品推荐

