devbox
木道寻08
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

day1: 二叉树

作者：木道寻08 | 2024-08-07 16:01:52

赞

踩

day1: 二叉树

1. 二叉树的层序遍历

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

示例：
二叉树：[3,9,20,null,null,15,7],

  1.     3
  2.    / \
  3.   9  20
  4.     /  \
  5.    15   7

返回其层次遍历结果：

  1. [
  2.   [3],
  3.   [9,20],
  4.   [15,7]
  5. ]

方法1:  这种方法 不好

  1. # Definition for a binary tree node.
  2. class TreeNode:
  3.     def __init__(self, x):
  4.         self.val = x
  5.         self.left = None
  6.         self.right = None
  7.  
  8. class Solution:
  9.     def levelOrder(self, root: TreeNode) -> List[List[int]]:
  10.         # 层序遍历 按层访问
  11.         # 队列  FIFO
  12.         queue_node = [root]
  13.         node_list = []
  14.         while queue_node:  # 队列非null， 一直循环
  15.             # 处理 根节点
  16.             queue_len = len(queue_node)
  17.             print(queue_len)
  18.             layer_queue = []
  19.             layer_list = []
  20.             for node in queue_node:
  21.                 if node:   
  22.                     layer_list.append(node.val)  # 没有按照队列操作，每层输出
  23.                     layer_queue.append(node.left)
  24.                     layer_queue.append(node.right)
  25.             if layer_list:
  26.                 node_list.append(layer_list)
  27.             queue_node = layer_queue
  28.         return node_list

方法2:  使用一个depth标记

  1. # Definition for a binary tree node.
  2. class TreeNode:
  3.     def __init__(self, x):
  4.         self.val = x
  5.         self.left = None
  6.         self.right = None
  7.  
  8. class Solution:
  9.     def levelOrder(self, root: TreeNode) -> List[List[int]]:
  10.         # 层序遍历 按层访问
  11.         # 队列  FIFO
  12.         queue_node = [(root, 0)] # 深度
  13.         cur_depth = 0  # 用来 确定是否换层
  14.         ans = []
  15.         temp = []
  16.         for node, depth in queue_node:
  17.             if node:
  18.                 # 判断 深度是否发生变化
  19.                 if cur_depth != depth:
  20.                     cur_depth = depth
  21.                     ans.append(temp)
  22.                     temp = []
  23.                 temp.append(node.val)
  24.                 queue_node.append((node.left, depth+1))
  25.                 queue_node.append((node.right, depth+1)) # 子节点 所以深度+1
  26.         if temp:
  27.             ans.append(temp)
  28.         return ans

 

2. 103. 二叉树的锯齿形层次遍历

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：
给定二叉树 [3,9,20,null,null,15,7],

  1.     3
  2.    / \
  3.   9  20
  4.     /  \
  5.    15   7

返回锯齿形层次遍历如下：

  1. [
  2.   [3],
  3.   [20,9],
  4.   [15,7]
  5. ]

方法1:

  1. # Definition for a binary tree node.
  2. class TreeNode:
  3.     def __init__(self, x):
  4.         self.val = x
  5.         self.left = None
  6.         self.right = None
  7.  
  8. class Solution:
  9.     def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
  10.         queue_node = [root]
  11.         node_list = []
  12.         flag = False # 为True 将每层node值结果倒序
  13.         # 思路：保持层序遍历不变， 只在 需要从右到左时： 每层节点node值 倒序一下即可
  14.         while queue_node:
  15.             layer_list = []
  16.             layer_node = []
  17.             for node in queue_node:
  18.                 if node:
  19.                     layer_list.append(node.val)
  20.                     layer_node.append(node.left)
  21.                     layer_node.append(node.right)
  22.             if flag:
  23.                 layer_list.reverse()
  24.             flag = not flag
  25.             if layer_list:
  26.                 node_list.append(layer_list)
  27.             queue_node = layer_node
  28.         return node_list

3. 94. 二叉树的中序遍历

给定一个二叉树，返回它的中序 遍历。

示例:

  1. 输入: [1,null,2,3]
  2.    1
  3.     \
  4.      2
  5.     /
  6.    3
  7.  
  8. 输出: [1,3,2]

 方法1:  递归

  1. # Definition for a binary tree node.
  2. class TreeNode:
  3.     def __init__(self, x):
  4.         self.val = x
  5.         self.left = None
  6.         self.right = None
  7.  
  8. class Solution:
  9.     def inorderTraversal(self, root: TreeNode) -> List[int]:
  10.         # 1.递归  中序遍历
  11.         if root:
  12.             left = self.inorderTraversal(root.left)
  13.             middle = left  +  [root.val]
  14.             right = self.inorderTraversal(root.right)
  15.             return middle + right
  16.         return []

方法2: 迭代

  1. class TreeNode:
  2.     def __init__(self, x):
  3.         self.val = x
  4.         self.left = None
  5.         self.right = None
  6.  
  7. class Solution:
  8.     def inorderTraversal(self, root: TreeNode) -> List[int]:
  9.         # 2.迭代算法  
  10.         value_list = []
  11.         p = root  # p 当作移动指针
  12.         stack = []  #栈：先进后出，  # 队列：先进先出；
  13.         while p or stack:
  14.             while p:  # 找左子树 一直找下去
  15.                 stack.append(p)
  16.                 p = p.left # p 移动 到 左孩子，直到为null
  17.             # p 为null，从stack中pop
  18.             p = stack.pop()
  19.             value_list.append(p.val)
  20.             # 处理右自子树
  21.             p = p.right
  22.         return value_list

4.  剑指 Offer 33. 二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

参考以下这颗二叉搜索树：

  1.      5
  2.     / \
  3.    2   6
  4.   / \
  5.  1   3

示例 1：

  1. 输入: [1,6,3,2,5]
  2. 输出: false

 示例 2：

  1. 输入: [1,3,2,6,5]
  2. 输出: true

解法1:

  1. class Solution:
  2.     def verifyPostorder(self, postorder: List[int]) -> bool:
  3.         '''
  4.         二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树：
  5.          若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 
  6.          若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 
  7.          它的左、右子树 也分别为二叉排序树。
  8.         '''
  9.         '方法1: 递归'
  10.         if len(postorder) <= 2:
  11.             return True
  12.  
  13.         '后序遍历结果规律： 最后一个为根结点， 从左到右遍历，找到第一个大于 根结点的值（索引：k） '
  14.         '左子树在：[0, k-1], 右子树在: [k, right-1], 即可递归'
  15.         '判断条件：若满足左子树值都小于根结点， 右子树值都大于根节点， 为True'
  16.         def verify(tree_list, left, right):
  17.             # 递归必须        本文内容由网友自发贡献，转载请注明出处：https://www.wpsshop.cn/w/木道寻08/article/detail/943363
    推荐阅读
    相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。