您现在的位置是:首页 > 正文

LeetCode--相关二叉树的例题与理解

2024-02-01 03:54:57阅读 2

1、相同的树
给定两个二叉树,编写一个函数来检验它们是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
示例 1:

输入:      
           1         1
          / \       / \
         2   3     2   3
        [1,2,3],   [1,2,3]
输出: true

示例 2:

输入:      1         1
          /           \
         2             2

        [1,2],     [1,null,2]
输出: false

示例 3:

输入:  
           1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]
输出: false

解题思路:广度遍历这棵树,比较这两个树的列表是否相同,但是需要注意的是:从左往右,也就是没有左子节点时用None表示。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        # 广度遍历
        def tree2list(t_head):
            if t_head is None:
                return None
            else:
                node_li = [t_head]
                val_li = [t_head.val]
                while node_li:
                    cur_node = node_li.pop(0)
                    if cur_node.left is None:
                        val_li.append(None)
                    else:
                        node_li.append(cur_node.left)
                        val_li.append(cur_node.left.val)
                    if cur_node.right is not None:
                        node_li.append(cur_node.right)
                        val_li.append(cur_node.right.val)
                return val_li
        p_li = tree2list(p)
        q_li = tree2list(q)
        return p_li==q_li

思路2:递归,深度遍历,对比相同节点位置的值是不是相同
1、 如果两棵树都是None,返回True
2、 非空的两棵树,使用递归,递归的退出条件相同位置的节点的值不同

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """        
        if not p and not q:
            return True
        elif p is not None and q is not None:
            if p.val == q.val:
                return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
            else:
                return False
        else:
            return None

2、对称二叉树
给定一个二叉树,检查它是否是镜像对称的。
例如,二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

   1
   / \
  2   2
   \   \
   3    3

说明:
如果你可以运用递归和迭代两种方法解决这个问题,会很加分。

解题思路:递归,左右两棵子树,相同位置的根节点的值相同,左子树的左子树与右子树的右子树是镜像,左子树的右子树与右子树的左子树是镜像关系,那么,这两棵子树就是镜像关系:

left.val == right.val and self.isMirror(left.right, right.left) and self.isMirror(left.left, right.right)

递归的退出条件:深度遍历到叶子节点时

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        return self.isMirror(root, root)
    def isMirror(self, left, right):
        if left is None and right is None:
            return True
        if left is None or right is None:
            return False
        return left.val == right.val and self.isMirror(left.right, right.left) and self.isMirror(left.left, right.right)

3、 二叉树的最大深度
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。
解题思路:
1、 广度遍历:列表里的元素:(当前节点的深度,节点对象),当(1,3)节点出栈的时候,比较当前的深度与初始设置饿最大深度的大小,然后3接连的左右节点进栈,一次类推,找出最后叶子节点的深度

(1,3)
(2,9)
(2,20)
(3,15)
(3,7)
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root is None:
            return 0
        else:
            q = [(1, root)]
            max_depth = 0
            while q:
                depth, cur_node = q.pop(0)
                if cur_node is not None:
                    max_depth = max(depth, max_depth)
                    q.append((depth + 1, cur_node.left))
                    q.append((depth + 1, cur_node.right))
            return max_depth

2、 递归,深度遍历,先遍历左子树,然后右子树,返回左右子树中深度最大的那一个
递归退出的条件:如果子树的根节点为None,退出,说明已经到叶子节点了

    3         3
   / \
  9  20       2
    /  \
   15   7     1
  /  \/  \    
   (None)     0

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root is None: 
            return 0 
        else: 
            left_height = self.maxDepth(root.left) 
            right_height = self.maxDepth(root.right) 
            return max(left_height, right_height) + 1

4、二叉树的层次遍历
给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
例如:
给定二叉树 [3,9,20,null,null,15,7],

    3           1层
   / \
  9  20         2层
    /  \
   15   7       3层

返回其自底向上的层次遍历为:

[
  [15,7],
  [9,20],
  [3]
]

解题思路:
1、广度遍历,但有所区别,这里并不是取出一个节点后把它的左右节点放到队列中,而是在这个队列里只存在一个层次的所有节点,然后遍历一下这个队列,获取里面所有元素的值放到一个列表里。所以这里实现的时候使用了一个临时队列,在遍历队列中一个层次的所有节点的同时,把这个层次里所有节点的左右子节点(也就是下一层次)放到这个临时队列中,然后让真正的队列引用这个临时队列。最后把所有层次的数值列表按顺序插入最后返回的列表。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def levelOrderBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        
        if root is None:
            return None
        else:
            query = [root]
            res = []
           
            while query:
                each_row = []
                temp = []
                for i in query:
                    each_row.append(i.val)
                    if i.left is not None:
                        temp.append(i.left)
                    if i.right is not None:
                        temp.append(i.right)
                query = temp
                res.insert(0, each_row)
            return res

2、递归,深度遍历(线序),保存根节点后遍历左子树,直到叶子节点后遍历右子树

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def levelOrderBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        def helper(node, depth, res):
            """
            利用前序遍历的思想
            """
            if not node:
                return   递归退出的条件
            # 超出递归的长度表明是新的一层,则新添加数组
            if depth < 0 and abs(depth) > len(res):
                res.insert(0, [])
            # 可以理解成每个node都能对应到树的depth
            res[depth].append(node.val)    递归过程中的业务处理
            if node.left:
                helper(node.left, depth-1, res)
            if node.right:
                helper(node.right, depth-1, res)    递归

        result = []
        helper(root, -1, result)
        return result

5、将有序数组转化成二叉搜索树
将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:

给定有序数组: [-10,-3,0,5,9],
一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树:

      0
     / \
   -3   9
   /   /
 -10  5
                                  

                                              [有序列表]
                                                 / \
解题思路:递归,将一个有序数组分成:        [左子树]、[根节点]、[右子树]
                                      / \                 / \
                       [左子树]、[根节点]、[右子树]     [左子树]、[根节点]、[右子树]
                        /\                  /\         /\               /\
                         …                  …                   …                   …  

1、 退出递归的条件
2、 执行递归前的业务处理
3、 递归(调用函数本身)

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        if not nums:
            return None     退出递归的条件

        mid = len(nums) // 2
        t = TreeNode(nums[mid])
        nums1 = nums[:mid]
        nums2 = nums[mid+1:]          业务处理

        t.left = self.sortedArrayToBST(nums1)
        t.right = self.sortedArrayToBST(nums2)       递归

        return t

6、平衡二叉树
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7

返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4

返回 false 。
解题思路:递归,包括两个递归函数,一个是判断左右子树是否是平衡二叉树,另一个是求解每棵子树的高度
1、 判断左右子树是否为平衡二叉树的递归函数:

  • 1、 退出递归的条件
  • 2、 在执行递归函数之前的业务逻辑处理(这里是判断左、右子树的高度差的绝对值是不是<=1)
  • 3、 递归

2、 返回树的高度的递归函数:

  • 1、 退出递归函数的条件
  • 2、 业务逻辑处理
  • 3、 递归

当然业务逻辑处理可有可无,可以在递归前、递归中、递归后

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        
        if abs(self.height(root.left)-self.height(root.right))>1:
            return False
        
        return self.isBalanced(root.left) and self.isBalanced(root.right)
        
    def height(self,root):
        if not root:
            return 0
        
        left = self.height(root.left) + 1
        right = self.height(root.right) + 1
        return max(right, left)

7、二叉树的最小深度
给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],

   3
   / \
  9  20
    /  \
   15   7

返回它的最小深度 2.
解题思路:递归,使用深度搜索,与上例的最大深度有点类似,但是不能只是简单的把return max(right, left)改成return min(right, left),这里有一种特殊的情况:

    3
   / 
  9 
 这种情况下的树的最小深度是2,不是1,所以在根节点的左右子节点都存在的情况下,
 return min(right, left)这种形式完全可以,当只有左节点或右节点时,返回的是包含
 左(右)节点的深度。

1、 递归退出的条件
2、 业务逻辑处理

  • 2.1、如果左右节点都存在:
  • 2.2、递归1
  • 2.3、如果只存在左节点:
  • 2.4、递归2
  • 2.5、如果只存在右节点:
  • 2.6、递归3
    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        def minDepth(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            if not root:
                return 0
    
            elif root.left and root.right:
                left = self.minDepth(root.left) + 1
                right = self.minDepth(root.right) + 1
                return min(left, right)
    
            elif root.left:
                left = self.minDepth(root.left) + 1
                return left
    
            elif root.right:
                right = self.minDepth(root.right) + 1
                return right
    
            else:
                return 1

思路二:广度搜索,当遍历到叶子节点时,返回当前的深度,然后比较出最小深度大小

(1,3) 根节点
(2,9) 叶子节点(深度为2)
(2,9) 叶子节点(深度为2)
(2,20)
(3,15) 叶子节点(深度为3)
(3.7) 叶子节点(深度为3)
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        queue = [(1, root)]
        min_depth = float('Inf')  # 正无穷
        while queue:
            depth, t = queue.pop()
            if not t.left and not t.right:
                min_depth = min(min_depth, depth)
                
            if t.left:
                queue.append((depth + 1, t.left))
            if t.right:
                queue.append((depth + 1, t.right))
                
        return min_depth

8、路径总和
给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树,以及目标和 sum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
解题思路:深度遍历,一直到叶子节点,判断和是否为sum值

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        if not root:
            return False    是否为空树

        if root.left is None and root.right is None:    叶子节点的判断
            return sum - root.val == 0

        return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)

网站文章

  • C#软件开发实例.私人订制自己的屏幕截图工具(七)添加放大镜的功能

    C#软件开发实例.私人订制自己的屏幕截图工具(七)添加放大镜的功能

    上一篇:C#软件开发实例.私人订制自己的屏幕截图工具(六)添加配置管理功能 由于截图时可能需要精确截取某一部分,所以需要放大镜的功能,这样截取的时候才更容易定位截图的位置。 添加PictureBox,name属性设置为“pictureBox_zoom”; 在“Form1_Load”事件处理函数中添加以下代码: //设置放大镜的大小 this.pictureBox_zoo...

    2024-02-01 03:54:27
  • 快速复现利用Log4j漏洞启动windows计算器

    快速复现利用Log4j漏洞启动windows计算器

    了解关于漏洞的描述,可以参考Vulnerability Affecting Multiple Log4j Versions Permits RCE Exploit根据文章描述,首先下载JDK1.8u1...

    2024-02-01 03:54:20
  • vue计算属性computed和侦听器watch的使用场景

    vue计算属性computed和侦听器watch的使用场景

    原文链接:https://dsx2016.com/?p=679 微信公众号: 大师兄2016 特点和区别 vue的computed选项主要用于同步对数据的处理,而watch选项主要用于事件的派发,可异步. 这两者都能达到同样的效果,但是基于它们各自的特点,使用场景会有一些区分. computed拥有缓存属性,只有当依赖的数据发生变化时,关联的数据才会变化,适用于计算或者格式化数据的...

    2024-02-01 03:54:13
  • java程序设计任务驱动教程学习笔记二

    java程序设计任务驱动教程学习笔记二

    一、标识符与关键字

    2024-02-01 03:53:43
  • Linux命令-详解more命令

    Linux命令-详解more命令

    2020年已经过去一半,最近欠下了好几篇博客。今天开始说6月的第一个博客,很简单,说一下more的命令。今天在敲命令的时候,忽然忘记咋写了,于是复习一下。

    2024-02-01 03:53:35
  • lftp的日志记录位置

    lftp的日志记录位置

    2024-02-01 03:53:28
  • FPGA:计算滑动求和----信号检测计算信号功率

    FPGA:计算滑动求和----信号检测计算信号功率

    FPGA:计算滑动求和----信号检测计算信号功率

    2024-02-01 03:53:21
  • docker安装oracle11g史上最全步骤(带图文) 热门推荐

    docker安装oracle11g史上最全步骤(带图文) 热门推荐

    因为在Linux中安装oracle非常麻烦,相信每个人也会遇到各种坑,为了一次装好,也方便将来直接可以导出镜像在各平台移植使用,所以选择用docker安装,并做详细记录,为以后需要之时拿来再看。 1、安装docker环境。 2、开始拉取oracle镜像 docker pull registry.cn-hangzhou.aliyuncs.com/helowin/oracle_...

    2024-02-01 03:52:50
  • iOS pickerView

    1.有几组 - (NSInteger)numberOfComponentsInPickerView:(UIPickerView *)pickerView 2.每组有几行 - (NSInteger)pickerView:(UIPickerView *)pickerView numberOfRowsInComponent:(NSInteger)component 3.显示内容

    2024-02-01 03:52:34
  • 数据结构【ArrayLIst】

    数据结构【ArrayLIst】

    ArrayList 方法的使用和介绍

    2024-02-01 03:52:28