LeetCode_day14-17 二叉树-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode_day14-17 二叉树。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

day14 144 145 94

144.二叉树的前序遍历

递归法

# 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: TreeNode) -> List[int]:
        if not root:   #2终止条件
            return []
        #3单层递归逻辑 中左右
        left = self.preorderTraversal(root.left)
        right = self.preorderTraversal(root.right)

        return  [root.val] + left +  right#传入参数及返回值

迭代法

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: TreeNode) -> List[int]:
        # 根结点为空则返回空列表
        if not root:
            return []
        stack = [root]#从根节点出发入栈
        result = []
        while stack:
            node = stack.pop()#节点为栈顶
            # 中结点先处理
            result.append(node.val)
            # 右孩子先入栈
            if node.right:#右节点不为空时
                stack.append(node.right)
            # 左孩子后入栈
            if node.left:#左节点不为空时
                stack.append(node.left)
        return result

统一迭代法

#迭代法前序遍历：中左右
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        result = []
        st= []
        if root:
            st.append(root)
        while st:
            node = st.pop()
            if node != None:#入栈顺序右中空
                if node.right: #右
                    st.append(node.right)
                if node.left: #左
                    st.append(node.left)
                st.append(node) #中
                st.append(None)
            else:
                node = st.pop()
                result.append(node.val)
        return result

145.二叉树的后序遍历

94.二叉树的中序遍历

递归

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if root is None:
            return []

        left = self.inorderTraversal(root.left)
        right = self.inorderTraversal(root.right)

        return left + [root.val] + right

迭代法

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        stack = []  # 不能提前将root结点加入stack中
        result = []
        cur = root#指针遍历二叉树
        while cur or stack:# 只要指针和栈不为空
            # 先迭代访问最底层的左子树结点
            if cur:#指针不为空，加入栈(栈记录指针遍历过的元素)
                stack.append(cur)#节点放入栈
                cur = cur.left#指针指向节点的左孩子
            # 到达最左结点后处理栈顶结点
            else:#节点无左孩子
                cur = stack.pop()#弹出栈顶元素，指针指向节点
                result.append(cur.val)
                # 取栈顶元素右结点
                cur = cur.right
        return result

统一迭代法

# 迭代法中序遍历：
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        result = []
        st = []
        if root:
            st.append(root)
        while st:
            node = st.pop()
            if node != None:#节点元素入栈
                if node.right:  # 添加右节点（空节点不入栈）
                    st.append(node.right)

                st.append(node)  # 添加中节点
                st.append(None)  # 中节点访问过，但是还没有处理，加入空节点做为标记。

                if node.left:  # 添加左节点（空节点不入栈）
                    st.append(node.left)
            else:  # 所有元素已入栈
                node = st.pop()  # 重新取出栈中元素
                result.append(node.val)  # 加入到结果集
        return result

day15 101 102 226

101.对称二叉树

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: TreeNode) -> bool:#判断是否对称
        if not root:
            return True
        return self.compare(root.left, root.right)#返回比较的结果

    def compare(self, left, right):
        # 首先排除空节点的情况
        if left == None and right != None:
            return False
        elif left != None and right == None:
            return False
        elif left == None and right == None:
            return True
        # 排除了空节点，再排除数值不相同的情况
        elif left.val != right.val:
            return False

        # 此时就是：左右节点都不为空，且数值相同的情况
        # 此时才做递归，做下一层的判断
        outside = self.compare(left.left, right.right)  # 左子树：左、 右子树：右
        inside = self.compare(left.right, right.left)  # 左子树：右、 右子树：左
        isSame = outside and inside  # 左子树：中、 右子树：中 （逻辑处理）
        return isSame

102.层序遍历

import collections

# 利用长度法
# 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]]:
        # 首先判断根节点是否存在，如果为空则返回一个空列表。
        if not root:
            return []
        # 如果根节点存在，则初始化一个deque（双端队列）对象，将根节点作为队列的唯一元素。
        queue = collections.deque([root])#类似 list 的容器，两端都能实现快速 append 和 pop (双端队列)
        # 同时初始化一个空列表result，用于存储每一层的节点值。
        result = []
        # 如果队列不为空，则进一步遍历二叉树的每一层。
        while queue:#记录一层的元素
            level = []
            #  for 循环来处理每一层的节点，遍历整个队列，
            #  将队列头部的节点（即当前层的第一个节点）出队，并记录节点的值。
            for _ in range(len(queue)):
                cur = queue.popleft()#队列左侧元素弹出
                level.append(cur.val)
                # 如果该节点存在左子节点，则将其左子节点入队
                if cur.left:
                    queue.append(cur.left)
                # 如果该节点存在右子节点，则将其右子节点入队
                if cur.right:
                    queue.append(cur.right)
            # 当 while 循环结束后，所有的层都已经被遍历完成。
            # 最后将每一层的节点值添加到 result 列表中，并将其返回即可。
            result.append(level)
        return result

226.翻转二叉树

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:#2结束条件
            return None
        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

day16 104 559 111 222

104.二叉树的最大深度

class solution:
    def maxdepth(self, root: TreeNode) -> int:
        return self.getdepth(root)

    def getdepth(self, node):
        if not node:
            return 0
        leftheight = self.getdepth(node.left)  # 左
        rightheight = self.getdepth(node.right)  # 右
        height = 1 + max(leftheight, rightheight)  # 中
        return height

559.n叉树的最大深度

class Solution:
    def maxDepth(self, root: 'Node') -> int:
        if not root:
            return 0

        max_depth = 1

        for child in root.children:
            max_depth = max(max_depth, self.maxDepth(child) + 1)

        return max_depth

111.二叉树的最小深度

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:#根节点为空
            return 0

        # 判断根节点是否为叶子节点（即左右子节点均为空）
        if not root.left and not root.right:
            return 1

        # 如果根节点不是叶子节点，则递归处理其左右子节点，并分别求出其最小深度
        # 递归过程中，如果左子节点或右子节点为空，则对应的最小深度应赋为正无穷，使得在取 min 的时候不影响结果。
        left_depth = float('inf')
        right_depth = float('inf')

        if root.left:#左节点不为空
            left_depth = self.minDepth(root.left)
        if root.right:#右节点不为空
            right_depth = self.minDepth(root.right)

        return 1 + min(left_depth, right_depth)

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

class Solution:
    def countNodes(self, root: TreeNode) -> int:
        if not root:
            return 0
        left = root.left
        right = root.right
        leftDepth = 0 #这里初始为0是有目的的，为了下面求指数方便
        rightDepth = 0
        # while 循环迭代计算左子树和右子树的深度
        while left: #求左子树深度
            left = left.left
            leftDepth += 1
        while right: #求右子树深度
            right = right.right
            rightDepth += 1
        # 如果leftDepth等于rightDepth，
        # 说明当前这个完全二叉树的最后一层节点数已经到达满二叉树的范围
        if leftDepth == rightDepth:
            return (2 << leftDepth) - 1 #注意(2<<1) 相当于2^2，所以leftDepth初始为0
        return self.countNodes(root.left) + self.countNodes(root.right) + 1

day17 110 257 404

110 平衡二叉树

# 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:# 判断是否是平衡二叉树
        if self.get_height(root) != -1:# 若高度差不是-1
            return True
        else:#已经不是平衡二叉树了
            return False

    # 求取给定二叉树的高度的功能
    def get_height(self, root: TreeNode) -> int:
        # 从底层开始处理，先写出 Base Case，即如果遇到空节点，则返回 0。
        # Base Case
        if not root:
            return 0
        # 进入满足先左后右的递归，先求解左子树的高度 left_height，
        # 如果返回值为 -1，则说明左子树不是平衡的，直接返回 -1，否则继续计算右子树的高度 right_height。
        # 左
        if (left_height := self.get_height(root.left)) == -1:
        #walrus operator（海象运算符）:=，可以同时进行赋值和判断操作。
            return -1
        # 右
        if (right_height := self.get_height(root.right)) == -1:
            return -1
        # 在“中”步骤中，判断左右子树的高度差是否大于 1.
        # 如果大于 1，则说明不是平衡二叉树，直接返回 -1，否则返回 1 加上左右子树中高度最大的值。
        if abs(left_height - right_height) > 1:
            return -1
        else:
            return 1 + max(left_height, right_height)

257 二叉树的所有路径

# 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
import copy
from typing import List, Optional


class Solution:
    # 接收一个 TreeNode 类型的参数 root，返回一个 List[str] 类型的结果。
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        # 先判断根节点 root 是否为空，如果为空则返回一个空列表
        if not root:
            return []
        # 否则新建一个空列表 result，
        # 并递归调用函数 generate_paths，将根节点以及两个空列表作为参数传入。
        result = []
        self.generate_paths(root, [], result)
        return result

    # 生成从根节点到叶子节点的所有路径
    # 参数包括一个节点 node，一个列表 path 以及一个列表 result。
    def generate_paths(self, node: TreeNode, path: List[int], result: List[str]) -> None:
        # 将节点 node 的值加入到列表 path 中，然后判断节点 node 是否为叶子节点。
        path.append(node.val)
        # 如果是叶子节点，则将列表 path 中的值以 ‘->’ 为分隔符连接成一个字符串，
        # 并将这个字符串加入到列表 result 中。
        if not node.left and not node.right:
            # map(str, path) 将列表 path 中的所有元素都转换成字符串
            # '->' 将字符串 '->' 作为连接符
            # join 将 path 中的所有字符串以 '->' 为间隔符连接成一个新的字符串
            result.append('->'.join(map(str, path)))
        # 否则，判断节点 node 的左右子节点是否存在，
        # 如果存在则递归调用函数 generate_paths，将左右子节点以及列表 path 的一个深拷贝作为参数传入递归函数中。
        if node.left:
            # 为什么要对 path 进行深拷贝呢？
            # 因为在递归调用函数 generate_paths 后，如果不对 path 进行深拷贝，那么 path 将会被更改，结果会导致之后的递归判断出现错误。
            self.generate_paths(node.left, copy.copy(path), result)
        if node.right:
            self.generate_paths(node.right, copy.copy(path), result)
        # 将列表 path 中的最后一个值弹出，以便回溯到上一个节点。
        path.pop()#回溯过程

404 左叶子之和文章来源地址https://www.toymoban.com/news/detail-554077.html

class Solution:
    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        # 检查根节点的左子节点是否为叶节点
        if root.left and not root.left.left and not root.left.right:
            left_val = root.left.val#收集左叶子节点的值
        else:#否则，递归计算节点左孩子的左叶子
            left_val = self.sumOfLeftLeaves(root.left)

        # 递归地计算右子树左叶节点的和
        right_val = self.sumOfLeftLeaves(root.right)

        return left_val + right_val

到了这里，关于LeetCode_day14-17 二叉树的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！