python 刷leetcode时如何传进去二叉树而非数组

python 刷leetcode时如何传进去二叉树而非数组

# 定义树
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 将数组转为二叉树
class Tree(object):
    def __init__(self):
        self.root = None
    def construct_tree(self, values=None):
        if not values:
            return None
        self.root = TreeNode(values[0])
        queue = deque([self.root])
        leng = len(values)
        nums = 1
        while nums < leng:
            node = queue.popleft()
            if node:
                node.left = TreeNode(values[nums]) if values[nums] else None
                queue.append(node.left)
                if nums + 1 < leng:
                    node.right = TreeNode(values[nums+1]) if values[nums+1] else None
                    queue.append(node.right)
                    nums += 1
                nums += 1
        return self.root


# leetcode实现

class Solution:
    def haspathsum(self, root: TreeNode, targetsum: int) -> bool:
        def isornot(root, targetsum) -> bool:
            if (not root.left) and (not root.right) and targetsum == 0:
                return True  # 遇到叶子节点，并且计数为0
            if (not root.left) and (not root.right):
                return False  # 遇到叶子节点，计数不为0
            if root.left:
                targetsum -= root.left.val  # 左节点
                if isornot(root.left, targetsum): return True  # 递归，处理左节点
                targetsum += root.left.val  # 回溯
            if root.right:
                targetsum -= root.right.val  # 右节点
                if isornot(root.right, targetsum): return True  # 递归，处理右节点
                targetsum += root.right.val  # 回溯
            return False
        if root == None:
            return False  # 别忘记处理空treenode
        else:
            print(root.val)
            return isornot(root, targetsum - root.val)

# main
a = Solution()
num = [5,4,8,11,None,13,4,7,2,None,None,None,1]
# 先实现二叉树
t = Tree()
root = t.construct_tree(num)
targetSum = 22
# 传进来的是二叉树
print(a.haspathsum(root, targetSum))