当前位置：首页 > article >正文

算法之二叉树

article 2025/1/19 20:57:34

二叉树

相关题目

判断根结点是等否于子结点之和
相同的树
对称二叉树
平衡二叉树

判断根结点是否等于子结点之和

在这里插入图片描述

总的来说，就是一个简单的二叉树的自我判断，就是只用判断根结点value的值与左右孩子value的值之间的和的关系

# 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 checkTree(self, root: Optional[TreeNode]) -> bool:
        return root.val == root.left.val + root.right.val

拓展为n个结点

在这里插入图片描述

深入理解递归[基础算法精讲09]

分析一下思路：

为什么会先看是否是叶子结点？因为多个结点的话，就应该使用递归来求解判断，而递归的问题的关键就在于你何时停止判断？==》到了叶子结点的判断就应该停止了

class Solution:
    def checkTree(self, root: Optional[TreeNode]) -> bool:
        if root.left is root.right:  # 递归边界：判断 root 是否为叶子节点
            return True
        return root.val == root.left.val + root.right.val and \
               self.checkTree(root.left) and self.checkTree(root.right)

相同的树

在这里插入图片描述

思路分析：对于树的判断，涉及到多个结点，所以还是考虑使用递归进行判断==》还是考虑从叶子结点出发：

* 左边或者右边是叶子结点的话==》我们使用 p is q 来判断，这样如果两边都没有叶子结点说明是符合的，就返回ture,否则就返回false
* 当两边都不是叶子结点的话==》我们就判断当前节点的值，并且递归调用方法判断当前结点的左结点和右结点是否相同

注意，对于递归调用方法，如果方法是类中的方法，得加上一个self进行调用

# 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 isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p is None or q is None:
            return p is q
        return p.val == q.val and self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)

对称二叉树

在这里插入图片描述

思路分析：可以在相同树的基础上进行调用相同树的代码，不过与相同树的左左右右不同，这个对称树的判断使用的是左右左右的对应

# 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 isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p is None or q is None:
            return p is q
        return p.val == q.val and self.isSameTree(p.left,q.right) and self.isSameTree(p.right,q.left)
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        return self.isSameTree(root.left,root.right)

平衡二叉树

平衡二叉树（Balanced Binary Tree）是一种特殊的二叉树，它的左右子树的高度差不超过 1，并且左右子树本身也是平衡二叉树。平衡二叉树的主要目的是保证树的深度尽可能小，从而提高查找、插入和删除等操作的效率。

在这里插入图片描述

算法的出发点？肯定是要计算左右子树的长度？

当然，肯定会使用到的是递归，那么递归的条件就是遇到结点是空(还不是叶子结点)，就返回的长度是0，然后我们会接着算该节点的左子树的深度，如果返回的长度是-1，说明就是不符合，需要提前退出递归，然后再计算右子树的深度，判断，如果右子树的深度为-1或者左右子树的深度的差的绝对值大于1，我们就返回1 ，最后我们返回左子树和右子树的长度的较大值再+1。在最外层的方法中，只用判断对于根结点调用这个计算长度的返回值是否等于-1即可

class Solution:
    def isBalance(self,root:Optional[TreeNode]) -> bool:
        def get_height(node:Optional[TreeNode]) -> int:
            if node is None: return 0
        	left_height = get_height(node.left)
            if left_height = -1 : return -1
        	right_height = get_height(node.rigth)
            if right_height = -1 or abs(left_height - right_height) > 1:
                return -1
            return max(left_height,right_height)
        return get_height(root) != -1