问题描述:【Tree】700. Search in a Binary Search Tree
解题思路:
这道题是给一棵二叉搜索树(BST),查找给定的结点。结点不存在返回 NULL。
利用 BST 的特点,进行二分查找即可。
Python3 实现:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def searchBST(self, root: TreeNode, val: int) -> TreeNode:
if not root:
return None
if root.val == val:
return root
elif root.val > val:
return self.searchBST(root.left, val)
elif root.val < val:
return self.searchBST(root.right, val)
问题描述:【Tree】872. Leaf-Similar Trees
解题思路:
这道题是给两棵树,判断它们的叶子序列(从左到右)是否相同。
将两棵树的叶子序列保存在 list 中,判断二者是否相同即可。
1、判断叶子的条件是 root.left == None and root.right == None
,返回 [root.val];
2、还要注意单子树的情况([1, 2] 或 [1, null, 2]),应该返回 [];
Python3 实现:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def leafSimilar(self, root1: TreeNode, root2: TreeNode) -> bool:
def leafSeq(root): # 得到树的叶子序列
if not root: # 防止单子树(如 [1,2] 或者 [1,null,2])
return []
if root.left == None and root.right == None: # 叶子
return [root.val]
return leafSeq(root.left) + leafSeq(root.right)
return leafSeq(root1) == leafSeq(root2)
问题描述:【Tree】897. Increasing Order Search Tree
解题思路:
这道题是给一棵二叉搜索树,将结点按照从小到大重新排列,构造一棵只有右结点的树。
先前序遍历将每个结点保存在 list 中,再构造只有右结点的树。构造右结点的树时,除了根结点 node 外,还要有一个工作指针 cur,在遍历 list 的过程中,cur 每次往右子树走(cur = cur.right
),最后返回 node 即可。
Python3 实现:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def increasingBST(self, root: TreeNode) -> TreeNode:
def in_order(root): # 中序遍历,保存结点
if not root:
return []
return in_order(root.left) + [TreeNode(root.val)] + in_order(root.right)
nodelist = in_order(root)
node = cur = nodelist[0] # node:指向根结点,cur:往右子树走
for i in range(1, len(nodelist)):
cur.right = nodelist[i]
cur = cur.right
return node
问题描述:【Tree】965. Univalued Binary Tree
解题思路:
这道题是给一棵二叉树,判断其是否是单值二叉树(所有结点值都相同)。
1、先将根结点的值作为目标值 tar,将 tar 也参与递归函数;
2、如果 root 为 None,返回 True;
3、如果 root.val == tar
,就递归左右子树,返回左右子树的判断结果;
4、否则返回 False。
Python3 实现:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isUnivalTree(self, root: TreeNode) -> bool:
if not root:
return True
self.tar = root.val # 目标值
return self.judge(root)
def judge(self, root):
if root == None:
return True
if root.val == self.tar:
return self.judge(root.left) and self.judge(root.right)
return False
问题描述:【DFS、Tree】1022. Sum of Root To Leaf Binary Numbers
解题思路:
这道题是给一个 01 二叉树,计算从根到叶子所有二进制路径表示的十进制数字的总和。
方法1(回溯法):
第一种容易想到的方法就是 DFS 回溯法,对树进行深度优先搜索,将每条路径 path 保存在 paths 列表中,每次找到一条路径的出口是遇到叶子结点。最后,对 paths 进行遍历,将每条路径 path 中的二进制转化为十进制数进行累加(如 int("0101", 2) = 5
)。这样做的空间复杂度为 O(n)。
Python3 实现:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def sumRootToLeaf(self, root: TreeNode) -> int:
def findPath(root, path):
if not root:
return
path += str(root.val) # 往当前路径中添加当前结点
if root.left == None and root.right == None: # 到叶子结点,增加一条路径
paths.append(path)
return
findPath(root.left, path)
findPath(root.right, path)
paths, sum = [], 0 # paths 保存每条路径
findPath(root, "")
for path in paths:
sum += int(path, 2) # 二进制转十进制
return sum
方法2(不使用额外空间的做法):
有没有不使用额外空间的做法呢?当然有。可以使用前缀和 presum。
在深度优先搜索的过程中,每增加一层,就修改当前路径的累加值,即 presum = presum * 2 + root.val
,如 1->0->1 (5)再碰到 1 就会执行 presum = presum * 2 + 1 = 11,刚好是 1->0->1->1(11)。
具体做法如下:
1、如果 root 为空,返回 0;
2、更新前缀累加和 presum = presum * 2 + 1
;
2、如果 root.left 或者 root.right 不为空,就递归求解左右子树路径和 return pathSum(root.left, presum) + pathSum(root.right, presum)
;
3、最后返回 presum 就是答案;
Python3 实现:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def sumRootToLeaf(self, root: TreeNode) -> int:
def pathSum(root, presum):
if not root:
return 0
presum = presum * 2 + root.val # 每增加一层修改当前路径累加值
if root.left or root.right: # 左右子树路径之和
return pathSum(root.left, presum) + pathSum(root.right, presum)
return presum # 到叶子结点
return pathSum(root, 0)
网友评论