二刷力扣--二叉树(2)

简介: 二刷力扣--二叉树(2)

226.翻转二叉树

给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。

使用递归解决。

  1. 确定函数参数和返回值
    函数参数为当前节点cur。无返回值。
def dd(cur):

  1. 确定终止条件。当前节点为空则终止。
if not cur:
  return
  1. 单层逻辑
    反转当前节点的左右,然后递归调用cur.left, cur.right
   def dd(cur):
            if not cur:
                return 
            cur.left, cur.right = cur.right, cur.left
            dd(cur.left)
            dd(cur.right)

完整代码如下:

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def dd(cur):
            if not cur:
                return 
            cur.left, cur.right = cur.right, cur.left
            dd(cur.left)
            dd(cur.right)
        dd(root)
        return root

101.对称二叉树

给你一个二叉树的根节点 root , 检查它是否轴对称。

这题用层序遍历很好做,只要判断每层是不是对称的就好了(空的节点添加一个特殊值方便判断对称)。

# 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def symmetric_list(lst):
            length = len(lst)
            i = 0
            j = length-1
            while i < j:
                if lst[i] != lst[j]:
                    return False
                i += 1
                j -= 1
            return True
        res = []
        if not root:
            return res
        queue = deque()
        queue.append(root)
        while len(queue) > 0:
            next_list = []
            length = len(queue)
            for i in range(length):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                    next_list.append(node.left.val)
                else:
                    next_list.append(-9999)

                if node.right:
                    queue.append(node.right)
                    next_list.append(node.right.val)
                else:
                    next_list.append(-9999)
            
            if not symmetric_list(next_list):
                return False

        return True

递归方式有点绕,因为要判断的是轴对称。

  1. 函数参数和返回值。
    参数是左子节点和右子节点。返回值是 bool值,表示是否当前节点是否轴对称。
def compare(left, right):
  1. 终止条件。
    左右节点全为空或某个为空时,则可以判断出当前节点的左右是否是对称的了。
if not left and not right:
  return True
elif not left or not right:
  return False  
  1. 单层逻辑
return    left.val == right.val and \
            compare(left.left, right.right) and compare(left.right, right.left) 

104.二叉树的最大深度

给定一个二叉树 root ,返回其最大深度。

层序遍历非常直接,遍历的层数就是深度。

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        res = []
        if not root:
            return res
        queue = deque()
        queue.append(root)
        while len(queue) > 0:
            sub_list = []
            length = len(queue) # 注意
            for i in range(length):
                node = queue.popleft()
                sub_list.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            res.append(sub_list)
        return res
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        res = self.levelOrder(root)
        
        return len(res)

递归更简单:

  1. 函数参数和返回值。
    参数为当前节点node。返回值为int值,表示节点的深度。
  2. 终止条件
    节点为空时,返回0.
  3. 单层逻辑
    max(左节点深度,右节点深度) +1
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        def depth(node):
            if not node:
                return 0
            leftDepth = depth(node.left)
            rightDepth = depth(node.right)
            return max(leftDepth, rightDepth)+1
        
        return depth(root)
  • 二叉树节点的深度:指从节点到该节点最长简单路径边的条数。
  • 二叉树节点的高度:指从该节点叶子节点最长简单路径边的条数。
    本题可以使用前序遍历(中左右),也可以使用后序遍历(左右中),使用前序求的就是深度,使用后序求的是高度
  • 而根节点的高度就是二叉树的最大深度,所以本题中我们通过后序求的根节点高度来求的二叉树最大深度。

111.二叉树的最小深度

给定一个二叉树,找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

这题层序遍历还是很简单,因为每遍历一层就对应深度+1。如果找到了叶子节点就可以终止遍历返回当前深度了。

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        queue  = deque()
        queue.append(root)
        depth = 0
        while queue:
            depth += 1
            length = len(queue)
            for i in range(length):
                node = queue.popleft()
                if all([not node.left, not node.right]):
                    return depth 
                for nextnode in [node.left, node.right]:
                    if nextnode:
                        queue.append(nextnode)

            
        return depth

递归方式。

递归方式和104求最大深度差很多。最小深度必须是根节点到叶子节点的长度,如果左子树为空,右子树不为空,则只能通过右子树到达叶子节点(1+rightDepth)。

递归公式:

  1. 函数参数和返回值。
    参数为当前节点node。返回值为int值,表示节点的深度。
  2. 终止条件
    节点为空时,返回0.
  3. 单层逻辑
  1. 如果只有右子树,返回 1+rightDepth
    如果只有左子树,返回 1+leftDepth
    否则,返回 min(左节点深度,右节点深度) +1
class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        def getDepth(node: Optional[TreeNode]) -> int:
            if  not node :
                return 0
            leftDepth = getDepth(node.left)
            rightDepth = getDepth(node.right)
            if not node.left and node.right :
                return 1+ rightDepth
            if not node.right and node.left:
                return 1+ leftDepth
            
            return  1 + min(leftDepth, rightDepth)
        
        return getDepth(root)

222.完全二叉树的节点个数

给你一棵 完全二叉树 的根节点 root ,求出该树的节点个数。

遍历一次就知道节点个数了。

但是这样就没有用到完全二叉树的性质。

完全二叉树只有两种情况,情况一:就是满二叉树,情况二:最后一层叶子节点没有满。

对于情况一,可以直接用 2^树深度 - 1 来计算,注意这里根节点深度为1。

对于情况二,分别递归左孩子,和右孩子,递归到某一深度一定会有左孩子或者右孩子为满二叉树,然后依然可以按照情况1来计算。

递归公式:

  1. 函数参数和返回值。
    参数是当前节点。返回值是当前节点为根节点的树的节点个数。
  2. 终止条件
    如果节点为None,返回0。
  3. 单层逻辑
    判断当前节点是不是满二叉树,是满二叉树则直接用公式2^树深度 - 1 返回节点数。否则递归处理左右子树,返回左子树节点数 + 右子树节点数 + 1。
class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        # 判断当前节点是不是满二叉树
        leftHeight, rightHeight = 0, 0
        left, right = root.left, root.right
        while left:
            left = left.left
            leftHeight += 1
        while right:
            right = right.right
            rightHeight += 1
        # 是满二叉树,则用公式计算
        if leftHeight == rightHeight:
            return (2 << leftHeight) -1
        # 否则递归处理left, right
        return self.countNodes(root.left) + self.countNodes(root.right) + 1


110.平衡二叉树

给定一个二叉树,判断它是否是高度平衡的二叉树。

一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 。

  • 二叉树节点的深度:指从节点到该节点最长简单路径边的条数。
  • 二叉树节点的高度:指从该节点叶子节点最长简单路径边的条数。

LeetCode上的不是按照路径数,而是按照节点数计算。

求深度可以从上到下去查 所以需要前序遍历(中左右),而高度只能从下到上去查,所以只能后序遍历(左右中)。

递归公式

  1. 函数参数和返回值
    参数为当前节点,返回值为节点的高度。返回值为-1时表示不是平衡二叉树。
  2. 终止条件
    节点为None,返回0。
  3. 单层逻辑
  1. 求左子树高度,如果为-1,则已经不平衡了,返回-1.
    求右子树高度,如果为-1,则已经不平衡了,返回-1.
    如果左右子树高度差>1,不平衡,返回-1.
    否则返回当前节点的高度,1 + max(leftDepth, rightDepth)
class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def getHeight(node):
            if not node:
                return 0
            leftDepth = getHeight(node.left)
            if leftDepth == -1: return -1
            rightDepth = getHeight(node.right)
            if rightDepth == -1: return -1
            

            if abs(leftDepth - rightDepth) > 1:
               return -1
            else:
               return  1 + max(leftDepth, rightDepth)
  
        return not getHeight(root) == -1

257.二叉树的所有路径

任意顺序 ,返回所有从根节点到叶子节点的路径。

递归+回溯。

递归公式

  1. 参数和返回值
    参数是当前节点、路径、(存放结果的数组)。返回值无。
  2. 终止条件
    到达叶子节点。
  3. 单层逻辑
    添加当前节点,递归(+回溯)遍历左子树和右子树。
class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        def traversal(cur, path, result):
            path.append(cur.val)   
            # 终止条件:到达叶子节点了     
            if not any([cur.left, cur.right]):
                sPath = ""
                for n in path:
                    sPath += str(n)
                    sPath += "->"
                sPath = sPath[:-2]
                result.append(sPath)
                return
            # 左子树 
            if cur.left:
                traversal(cur.left, path, result)
                path.pop() # 回溯
            # 右子树  
            if cur.right:
                traversal(cur.right, path, result)
                path.pop()
        
        result = []
        path = []
        if not root:
            return result
        traversal(root, path, result)
        return result


404.左叶子之和

给定二叉树的根节点 root ,返回所有左叶子之和。

左叶子:是父节点的左节点,并且是叶子节点。

递归公式:

  1. 函数参数和返回值
    参数是当前节点,返回值是当前节点的左叶子之和。
  2. 终止条件
    当前节点为None,返回0.
  3. 单层逻辑
    如果当前节点是左叶子,则要加入当前节点的值。然后加上左子树的左叶子和,右子树的左叶子和。
class Solution:
    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        def getLeft(node):
            if not node:
                return 0
            leftValue = getLeft(node.left)
            rightValue = getLeft(node.right)
            midValue = 0
            # 左叶子:
            # 它是父节点的左节点,同时它是叶子节点
            if node.left and node.left.left == None and node.left.right ==None:
                midValue =  node.left.val 
            return midValue + leftValue + rightValue
        
        return getLeft(root)

513.找树左下角的值

给定一个二叉树的 根节点 root,请找出该二叉树的 最底层 最左边 节点的值。

层序遍历比较简单,遍历完然后获取最后一层的第一个节点。

# 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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        res = []
        if not root:
            return res
        queue  = deque()
        queue.append(root)
        while queue:
            sub_list  = []
            length = len(queue)
            for i in range(length):
                node = queue.popleft()
                sub_list.append(node.val)
                for nextnode in [node.left, node.right]:
                    if nextnode:
                        queue.append(nextnode)

            res.append(sub_list)
        return res
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        return self.levelOrder(root)[-1][0]

递归方式。

递归找最底层最左的节点,需要知道层数。

递归公式:

  1. 函数参数和返回值。
    参数是当前节点和当前层数。
  2. 终止条件
    到达叶子节点。
  3. 单层逻辑
    递归处理左子树和右子树,深度+1.
class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        maxDepth = -11111 # 最大深度
        maxLeftValue = 0 # 最深层 最左的节点值
        def traversal(root, depth):
            nonlocal maxDepth, maxLeftValue
            # 终止条件: 到达叶子
            if not root.left and not root.right:
            # 深度是最深的,更新答案
                if depth > maxDepth:
                    maxDepth = depth
                    maxLeftValue = root.val
                return
            # 递归处理左右
            if root.left:
                traversal(root.left, depth+1) # 隐藏回溯
            if root.right:
                traversal(root.right, depth+1)
            return 
        
        traversal(root,0)
        return maxLeftValue

112.路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false

递归公式:

  1. 函数参数和返回值
    参数:当前节点root,目标和targetSum。
    返回值:bool值,表示是否满足题目要求。
  2. 终止条件:
    当前节点为None,返回False
  3. 单层逻辑:
    如果是叶子节点,判断当前值和目标值是否相等。
    否则对左、右子数递归判断。
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        if not root.left and not root.right:
            return root.val == targetSum
        return self.hasPathSum(root.left, targetSum-root.val) or self.hasPathSum(root.right, targetSum-root.val)

相关文章
|
13天前
|
算法
刷算法Leetcode---9(二叉树篇Ⅲ)
刷算法Leetcode---9(二叉树篇Ⅲ)
12 3
|
1月前
|
存储 算法 Python
二刷力扣--哈希表
二刷力扣--哈希表
|
1月前
|
算法
二刷力扣--二叉树(3)
二刷力扣--二叉树(3)
|
1月前
二刷力扣--二叉树(1)基础、遍历
二刷力扣--二叉树(1)基础、遍历
|
1月前
|
存储 算法 Python
二刷力扣--栈和队列
二刷力扣--栈和队列
|
1月前
|
算法 索引 Python
二刷力扣--字符串
二刷力扣--字符串
|
1月前
|
Java Python
二刷力扣--链表
二刷力扣--链表
|
1月前
|
C++ Python
二刷力扣--数组
二刷力扣--数组
|
1月前
|
存储 算法 数据可视化
力扣156题最全解法:如何上下翻转二叉树(递归与迭代方法详解,附图解)
力扣156题最全解法:如何上下翻转二叉树(递归与迭代方法详解,附图解)
|
1月前
|
算法 数据可视化 数据挖掘
LeetCode题目104: 二叉树的最大深度(递归\迭代\层序遍历\尾递归优化\分治法实现 )
LeetCode题目104: 二叉树的最大深度(递归\迭代\层序遍历\尾递归优化\分治法实现 )
LeetCode题目104: 二叉树的最大深度(递归\迭代\层序遍历\尾递归优化\分治法实现 )