当前位置:   article > 正文

深度优先搜索算法(DFS)-二叉树的一些基本问题汇总_二叉树深度优先搜索

二叉树深度优先搜索

深度优先搜索算法(DFS)-二叉树的一些基本问题汇总



前言

DFS,核心思想“查到底,无果则回溯”;现实问题中,有许多问题其实可以抽象转化为树或图的搜索与遍历。一般实现的方式有:递归以及堆栈,本博客都是以递归实现。


一、二叉树的前序、中序、后序遍历

lc144前序
lc145后序
lc94中序

给你二叉树的根节点 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def preorder(root:TreeNode):
            if not root: return
            res.append(root.val) #先存根节点的值
            preorder(root.left) #随后递归左子树
            preorder(root.right) #同理递归右子树
        res = list()
        preorder(root)
        return res
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

代码如下(后序):

# 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 postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def postorder(root: TreeNode):
            if not root: return
            postorder(root.left) #递归左子树
            postorder(root.right) #递归右子树
            res.append(root.val) #跟留在最后
        res = list()
        postorder(root)
        return res
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

代码如下(中序):

# 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 inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def inorder(root: TreeNode):
            if not root: return 
            inorder(root.left)
            res.append(root.val)
            inorder(root.right)
        res = list()
        inorder(root)
        return res
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

二、二叉树的最大、最小深度

lc104二叉树地最大深度
lc111二叉树的最小深度

2.1 二叉树的最大深度

求得二叉树的最大深度,对于根节点来说,选择其左右子树中较深的子树的深度再加上根节点这一层的深度1, 即为这棵二叉树的最大深度。可见,可以将原问题拆分成不断求子树深度的问题。求子树深度可以视为原始问题的子问题,在解决规模较大的问题前,需要先解决规模较小的子问题。

通过递归调用的方式,当节点为空时,将0返回给上层,也相当于是递归的终止条件。

代码如下(最大深度):

# 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 maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0 #递归的终止条件
        else:
            left_high = self.maxDepth(root.left)
            right_high = self.maxDepth(root.right)
            return max(left_high, right_high) + 1
    
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

2.2 最小深度

最大深度还是比较容易理解的,但最小深度并不是简单的把 max(left_high, right_high) + 1 换成 min(left_high, right_high) + 1 就好,如果这么做地话,结果只能得到最小深度为 1,显然不对嘛。
当一颗二叉树只有左子树或右子树时,不能忽略没有子树地一侧;
例如,只有左子树时(如下图所示),右子树(空)就不应该返回给上层,只需将左子树深度+1 返回即可,对只有右子树同理;
在这里插入图片描述

if not root.left:
    return self.minDepth(root.right) + 1
if not root.right:
    return self.minDepth(root.left) + 1
  • 1
  • 2
  • 3
  • 4

代码如下(最小深度):

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:return 0 #递归终止条件
        if not root.left:
            return self.minDepth(root.right) + 1
        if not root.right:
            return self.minDepth(root.left) + 1
        return min(self.minDepth(root.left), self.minDepth(root.right)) + 1
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

三、平衡二叉树

lc110平衡二叉树

给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

代码如下(自上而下地递归):

# 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 isBalanced(self, root: TreeNode) -> bool:
        def maxDepth(root):
            if not root:return 0
            left_depth = maxDepth(root.left)
            right_depth = maxDepth(root.right)
            return max(left_depth, right_depth) + 1

        if not root:return True
        return self.isBalanced(root.left) and self.isBalanced(root.right) and abs(maxDepth(root.left)-maxDepth(root.right)) <= 1

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

为了减少重复地计算,采用自下而上地递归方法。有点类似于后序遍历。当发现任一子树不平衡时,及时地反馈。

代码如下(自下而上地递归):

# 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 isBalanced(self, root: TreeNode) -> bool:
        def height(root):
            if not root:return 0
            left_height = height(root.left)
            right_height = height(root.right)
            if left_height == -1 or right_height == -1 or abs(left_height - right_height) > 1:
                return -1 #及时地反馈
            else:
                return max(left_height, right_height) + 1
        return height(root) >= 0


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

四、二叉树的所有路径

lc257二叉树的所有路径
给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
在这里插入图片描述
输入:root = [1,2,3,null,5]
输出:[“1->2->5”,“1->3”]

class Solution(object):
    def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        def constr_path(root,res,str_):
            if not root:return #
            if root:
                str_ += str(root.val)
                if not root.left and not root.right: #当前节点为叶子节点时
                    res.append(str_) #遍历到最后了,把路径保存在列表中
                else: #如果不是叶子节点,则继续遍历
                    str_ += '->'
                    constr_path(root.left,res,str_)
                    constr_path(root.right,res,str_)
        res = []
        str_ = ''
        constr_path(root,res,str_)
        return res
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/681253
推荐阅读
相关标签
  

闽ICP备14008679号