• 算法day15|10,226,101

    层序遍历

    102. Binary Tree Level Order Traversal

    1. # Definition for a binary tree node.
    2. # class TreeNode(object):
    3. #     def __init__(self, val=0, left=None, right=None):
    4. #         self.val = val
    5. #         self.left = left
    6. #         self.right = right
    7. class Solution(object):
    8.     def levelOrder(self, root):
    9.         """
    10.         :type root: TreeNode
    11.         :rtype: List[List[int]]
    12.         """
    13.         
    14.         results = []
    15.         if not root:
    16.             return results
    17.         
    18.         que = deque()
    19.         que.append(root)
    20.         while len(que) != 0:
    21.             size = len(que)
    22.             result = []
    23.             while size >0:
    24.                 node = que.popleft()
    25.                 result.append(node.val)
    26.                 if node.left is not None:
    27.                     que.append(node.left)
    28.                 if node.right is not None:
    29.                     que.append(node.right)
    30.                 size -= 1
    31.             results.append(result)
    32.         return results

    二刷：

    未ac。使用成栈了，然后搞错了。然后少考虑了root未空的情况。方法是写对了

    1. class Solution:
    2.     def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
    3.         result =[]
    4.         if not root:
    5.             return result
    6.         que = deque()
    7.         que.append(root)
    8.         while que:
    9.             #统计栈里面的size
    10.             size = len(que)
    11.             temp = []
    12.             while size > 0:
    13.                 temp1 = que.popleft()
    14.                 temp.append(temp1.val)
    15.                 if temp1.left is not None:
    16.                     que.append(temp1.left)
    17.                 if temp1.right is not None:
    18.                     que.append(temp1.right)
    19.                 size -= 1
    20.             result.append(temp)
    21.         return result

    三刷

    1. var levelOrder = function(root) {
    2.     // 层序遍历
    3.     let stack = []
    4.     let result = []
    5.     if(root === null){
    6.         return result
    7.     }
    8.     stack.push(root)
    9.     while(stack.length){
    10.         let size = stack.length
    11.         let temp = []
    12.         for(let i = 0; i < size; i++){
    13.             let node = stack.shift()
    14.             if(node){
    15.                 temp.push(node.val)
    16.                 if(node.left){
    17.                     stack.push(node.left)
    18.                 }
    19.                 if(node.right){
    20.                     stack.push(node.right)
    21.                 }
    22.             }
    23.         }
    24.         result.push(temp)
    25.     }
    26.     return result
    27. };

    107. Binary Tree Level Order Traversal II

    1. class Solution(object):
    2.     def levelOrderBottom(self, root):
    3.         """
    4.         :type root: TreeNode
    5.         :rtype: List[List[int]]
    6.         """
    7.         if root is None:
    8.             return []
    9.         results =[]
    10.         que = deque()
    11.         que.append(root)
    12.         while len(que) != 0:
    13.             size = len(que)
    14.             result = []
    15.             
    16.             while size >0:
    17.                 node = que.popleft()
    18.                 result.append(node.val)
    19.                 if node.left is not None:
    20.                     que.append(node.left)
    21.                 if node.right is not None:
    22.                     que.append(node.right)
    23.                 size -= 1
    24.             results.append(result)
    25.         return reversed(results)

    二刷：

    ac了

    1. class Solution:
    2.     def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
    3.         #就是直接正着写，结果倒叙
    4.         que = deque()
    5.         result = []
    6.         que.append(root)
    7.         if not root:
    8.             return result
    9.         while que:
    10.             size = len(que)
    11.             temp = []
    12.             while size>0:
    13.                 node = que.popleft()
    14.                 temp.append(node.val)
    15.                 if node.left is not None:
    16.                     que.append(node.left)
    17.                 if node.right is not None:
    18.                     que.append(node.right)
    19.                 size -= 1
    20.             result.append(temp)
    21.         new_result = []
    22.         for i in range(len(result)-1,-1,-1):
    23.             new_result.append(result[i])
    24.         return new_result

    三刷

    1. var levelOrderBottom = function(root) {
    2.     // 层序遍历
    3.     let stack = []
    4.     let result = []
    5.     if(root === null){
    6.         return result
    7.     }
    8.     stack.push(root)
    9.     while(stack.length){
    10.         let size = stack.length
    11.         let temp = []
    12.         for(let i = 0; i < size; i++){
    13.             let node = stack.shift()
    14.             if(node){
    15.                 temp.push(node.val)
    16.                 if(node.left){
    17.                     stack.push(node.left)
    18.                 }
    19.                 if(node.right){
    20.                     stack.push(node.right)
    21.                 }
    22.             }
    23.         }
    24.         result.unshift(temp)
    25.     }
    26.     console.log(result)
    27.     return result
    28. };

    199.二叉树的右视图

    1. class Solution(object):
    2.     def rightSideView(self, root):
    3.         """
    4.         :type root: TreeNode
    5.         :rtype: List[int]
    6.         """
    7.         if root is None:
    8.             return []
    9.         que = deque()
    10.         que.append(root)
    11.         result = []
    12.         while len(que)!=0:
    13.             size = len(que)
    14.             node = que[-1]
    15.             result.append(node.val)
    16.             while size > 0:
    17.                 node = que.popleft()
    18.                 if node.left:
    19.                     que.append(node.left)
    20.                 if node.right:
    21.                     que.append(node.right)
    22.                 size -= 1
    23.         return result

    二刷：

    未ac

    1. if root is None:
    2.             return []
    3.         que = deque()
    4.         que.append(root)
    5.         result = []
    6.         while len(que)!=0:
    7.             size = len(que)
    8.             node = que[-1]
    9.             print(node)
    10.             result.append(node.val)
    11.             while size > 0:
    12.                 node = que.popleft()
    13.                 if node.left:
    14.                     que.append(node.left)
    15.                 if node.right:
    16.                     que.append(node.right)
    17.                 size -= 1
    18.         return result

    三刷

    1. var rightSideView = function(root) {
    2.     let stack = []
    3.     let result = []
    4.     if(root === null){
    5.         return result
    6.     }
    7.     stack.push(root)
    8.     while(stack.length){
    9.         let size = stack.length
    10.         let node = stack[stack.length-1]
    11.         result.push(node.val)
    12.         for(let i = 0; i < size; i++){
    13.             let node = stack.shift()
    14.             if(node){
    15.                 if(node.left){
    16.                     stack.push(node.left)
    17.                 }
    18.                 if(node.right){
    19.                     stack.push(node.right)
    20.                 }
    21.             }
    22.         }
    23.     }
    24.     console.log(result)
    25.     return result
    26. };

    637.二叉树的层平均值

    1. class Solution(object):
    2.     def averageOfLevels(self, root):
    3.         """
    4.         :type root: TreeNode
    5.         :rtype: List[float]
    6.         """
    7.         from numpy import *
    8.         if root is None:
    9.             return []
    10.         results = []
    11.         que = deque()
    12.         que.append(root)
    13.         while len(que) != 0:
    14.             size = len(que)
    15.             result = []
    16.             while size>0:
    17.                 node = que.popleft()
    18.                 result.append(node.val)
    19.                 if node.left:
    20.                     que.append(node.left)
    21.                 if node.right:
    22.                     que.append(node.right)
    23.                 size -= 1
    24.             results.append(mean(result))
    25.         return results

    二刷：ac

    三刷

    1. var averageOfLevels = function(root) {
    2.     let stack = []
    3.     let result = []
    4.     if(root === null){
    5.         return result
    6.     }
    7.     stack.push(root)
    8.     while(stack.length){
    9.         let size = stack.length
    10.         let temp = []
    11.         for(let i = 0; i < size; i++){
    12.             let node = stack.shift()
    13.             temp.push(node.val)
    14.             if(node){
    15.                 if(node.left){
    16.                     stack.push(node.left)
    17.                 }
    18.                 if(node.right){
    19.                     stack.push(node.right)
    20.                 }
    21.             }
    22.         }
    23.         let avg = temp.reduce((a,b)=>a+b)/temp.length
    24.         result.push(avg)
    25.     }
    26.     console.log(result)
    27.     return result
    28. };

    429. N-ary Tree Level Order Traversal

    1. class Solution(object):
    2.     def levelOrder(self, root):
    3.         """
    4.         :type root: Node
    5.         :rtype: List[List[int]]
    6.         """
    7.         results = []
    8.         if not root:
    9.             return results
    10.         
    11.         que = deque()
    12.         que.append(root)
    13.         while len(que) != 0:
    14.             size = len(que)
    15.             result = []
    16.             while size >0:
    17.                 node = que.popleft()
    18.                 result.append(node.val)
    19.                 #存储的是一个列表
    20.                 if node.children is not None:
    21.                 #使用库函数，自动扩展队列
    22.                     que.extend(node.children)
    23.                 size -= 1
    24.             results.append(result)
    25.         return results

    二刷：

    未ac。可以注意到children的list，所以可使用之前我们做过数组的那一章节的extend函数进行拓展。

    三刷

    1. var levelOrder = function(root) {
    2.     let stack = []
    3.     let result = []
    4.     if(root === null){
    5.         return result
    6.     }
    7.     stack.push(root)
    8.     while(stack.length){
    9.         let size = stack.length
    10.         let temp = []
    11.         for(let i = 0; i < size; i++){
    12.             let node = stack.shift()
    13.             if(node){
    14.                 temp.push(node.val)
    15.                 if(node.children){
    16.                     for(let index in node.children){
    17.                         stack.push(node.children[index])
    18.                     }
    19.                 }
    20.             }
    21.         }
    22.         result.push(temp)
    23.     }
    24.     console.log(result)
    25.     return result
    26.     
    27. };

    515. Find Largest Value in Each Tree Row

    1.         results = []
    2.         if not root:
    3.             return results
    4.         
    5.         que = deque()
    6.         que.append(root)
    7.         while len(que) != 0:
    8.             size = len(que)
    9.             result = []
    10.             while size >0:
    11.                 node = que.popleft()
    12.                 result.append(node.val)
    13.                 if node.left:
    14.                     que.append(node.left)
    15.                 if node.right:
    16.                     que.append(node.right)
    17.                 size -= 1
    18.             maxx = max(result)
    19.             results.append(maxx)
    20.         return results

    二刷：

    ac

    三刷

    1. var largestValues = function(root) {
    2.     let stack = []
    3.     let result = []
    4.     if(root === null){
    5.         return result
    6.     }
    7.     stack.push(root)
    8.     while(stack.length){
    9.         let size = stack.length
    10.         let temp = []
    11.         for(let i = 0; i < size; i++){
    12.             let node = stack.shift()
    13.             if(node){
    14.                 temp.push(node.val)
    15.                 if(node.left){
    16.                     stack.push(node.left)
    17.                 }
    18.                 if(node.right){
    19.                     stack.push(node.right)
    20.                 }
    21.             }
    22.         }
    23.         result.push(Math.max(...temp))
    24.     }
    25.     console.log(result)
    26.     return result
    27. };

    116.填充每个节点的下一个右侧节点指针

    这道题题目的意思是讲将右侧节点指向左侧，所以得给他加上一个next 的指向

    1. class Solution(object):
    2.  
    3.     def connect(self, root):
    4.         """
    5.         :type root: Node
    6.         :rtype: Node
    7.         """
    8.         if root is None:
    9.             return None
    10.         
    11.         queue = [root]
    12.         while queue:
    13.             n = len(queue)
    14.             for i in range(n):
    15.                 node = queue.pop(0)
    16.                 if node.left:
    17.                     queue.append(node.left)
    18.                 if node.right:
    19.                     queue.append(node.right)
    20.                 if i == n - 1:
    21.                     break
    22.                 node.next = queue[0]
    23.         return root

    二刷：

    未ac

    三刷

    1. var connect = function(root) {
    2.     let stack = []
    3.     if(root === null){
    4.         return null
    5.     }
    6.     stack.push(root)
    7.     while(stack.length){
    8.         let size = stack.length
    9.         for(let i = 0; i < size; i++){
    10.             let node = stack.shift()
    11.             if (i < size - 1) {
    12.                 // 新的队头是node的右边元素
    13.                 node.next = stack[0];
    14.             }
    15.             if(node){
    16.                 if(node.left){
    17.                     stack.push(node.left)
    18.                 }
    19.                 if(node.right){
    20.                     stack.push(node.right)
    21.                 }
    22.             }  
    23.         } 
    24.     }
    25.     return root
    26. };

    117.填充每个节点的下一个右侧节点指针II

    1.  
    2. class Solution(object):
    3.     def connect(self, root):
    4.         """
    5.         :type root: Node
    6.         :rtype: Node
    7.         """
    8.         if root is None:
    9.             return None
    10.         
    11.         queue = [root]
    12.         while queue:
    13.             n = len(queue)
    14.             for i in range(n):
    15.                 node = queue.pop(0)
    16.                 if node.left:
    17.                     queue.append(node.left)
    18.                 if node.right:
    19.                     queue.append(node.right)
    20.                 if i == n - 1:
    21.                     break
    22.                 node.next = queue[0]
    23.         return root

    二刷：

    未ac。

    不知道如何指向后面的元素。需要利用que自己的一个属性。

    1. class Solution:
    2.     def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
    3.         if not root:
    4.             return 
    5.         que = deque()
    6.         que.append(root)
    7.         while len(que) != 0:
    8.             size = len(que)
    9.             while size >0:
    10.                 node = que.popleft()
    11.                 if node.left:
    12.                     que.append(node.left)
    13.                 if node.right:
    14.                     que.append(node.right)
    15.                 if size == 1:
    16.                     break
    17.                 node.next = que[0]
    18.                 size -= 1
    19.         return root

    三刷

    1. let stack = []
    2.     if(root === null){
    3.         return null
    4.     }
    5.     stack.push(root)
    6.     while(stack.length){
    7.         let size = stack.length
    8.         for(let i = 0; i < size; i++){
    9.             let node = stack.shift()
    10.             if (i < size - 1) {
    11.                 // 新的队头是node的右边元素
    12.                 node.next = stack[0];
    13.             }
    14.             if(node){
    15.                 if(node.left){
    16.                     stack.push(node.left)
    17.                 }
    18.                 if(node.right){
    19.                     stack.push(node.right)
    20.                 }
    21.             }  
    22.         } 
    23.     }
    24.     return root

    104.二叉树的最大深度

    1. class Solution(object):
    2.     def maxDepth(self, root):
    3.         """
    4.         :type root: TreeNode
    5.         :rtype: int
    6.         """
    7.         count = 0
    8.         if not root:
    9.             return count
    10.         que = deque()
    11.         que.append(root)
    12.         while len(que) != 0:
    13.             size = len(que)
    14.             while size >0:
    15.                 node = que.popleft()
    16.                 if node.left is not None:
    17.                     que.append(node.left)
    18.                 if node.right is not None:
    19.                     que.append(node.right)
    20.                 size -= 1
    21.             count += 1
    22.         return count

    二刷：

    ac

    三刷

    1. var maxDepth = function(root) {
    2.     let stack = []
    3.     if(root === null){
    4.         return null
    5.     }
    6.     stack.push(root)
    7.     let count = 0
    8.     while(stack.length){
    9.         let size = stack.length
    10.         for(let i = 0; i < size; i++){
    11.             let node = stack.shift()
    12.             if(node){
    13.                 if(node.left){
    14.                     stack.push(node.left)
    15.                 }
    16.                 if(node.right){
    17.                     stack.push(node.right)
    18.                 }
    19.             }  
    20.         } 
    21.         count ++
    22.     }
    23.     return count
    24. };

    111.二叉树的最小深度(这题没想出来)

    当左右节点为空节点的时候，这就是最深度最低的

    1. class Solution(object):
    2.     def minDepth(self, root):
    3.         """
    4.         :type root: TreeNode
    5.         :rtype: int
    6.         """
    7.         if root is None:
    8.             return 0
    9.         que = [(root,1)]
    10.         
    11.         while len(que) != 0:
    12.             node,depth = que.pop(0)
    13.             #终止条件，当都为空，跳出循环
    14.             if node.left is None and node.right is None:
    15.                 return depth
    16.             if node.left is not None:
    17.                 que.append((node.left,depth+1))
    18.             if node.right is not None:
    19.                 que.append((node.right,depth+1))
    20.         #遍历完毕后，如果都没有找到的话，返回0
    21.         return 0

    重点： 

    不要忘记有空值得情况

    que[0] 是要出队的

    que[-1]是刚入队的

    题目链接/文章讲解/视频讲解：代码随想录 

    二刷：ac。但是方法好像不对啊。我的方法是，如果遇到左右节点为空，就是最小的。跟上面的方法意思是类似的。只是它使用了个数组来记录

    1. class Solution:
    2.     def minDepth(self, root: Optional[TreeNode]) -> int:
    3.         if not root:
    4.             return 0
    5.         que = deque()
    6.         que.append(root)
    7.         result = 0
    8.         while len(que) != 0:
    9.             size = len(que)
    10.             while size > 0:
    11.                 node = que.popleft()
    12.                 if node.left:
    13.                     que.append(node.left)
    14.                 if node.right:
    15.                     que.append(node.right)
    16.                 if node.right is None and node.left is None:
    17.                     return result+1
    18.                 size -= 1
    19.             result += 1
    20.         return result
    1. class Solution:
    2.     def minDepth(self, root: Optional[TreeNode]) -> int:
    3.         if not root:
    4.             return 0
    5.         que = deque()
    6.         que.append([root,1])
    7.         result = 0
    8.         while len(que) != 0:
    9.             size = len(que)
    10.             while size > 0:
    11.                 node,depth = que.popleft()
    12.                 if node.left:
    13.                     que.append([node.left,depth+1])
    14.                 if node.right:
    15.                     que.append([node.right,depth+1])
    16.                 if node.right is None and node.left is None:
    17.                     return depth
    18.                 size -= 1
    19.         return 0
    1. var minDepth = function(root) {
    2.     let stack = []
    3.     if(root === null){
    4.         return null
    5.     }
    6.     stack.push(root)
    7.     let count = 0
    8.     while(stack.length){
    9.         let size = stack.length
    10.         for(let i = 0; i < size; i++){
    11.             let node = stack.shift()
    12.             if(node){
    13.                 if(node.left){
    14.                     stack.push(node.left)
    15.                 }
    16.                 if(node.right){
    17.                     stack.push(node.right)
    18.                 }
    19.                 if(node.right ===null&& node.left===null){
    20.                     return count +1
    21.                 }
    22.             }  
    23.         } 
    24.         count ++
    25.     }
    26.     return count
    27. };

    226.翻转二叉树 （优先掌握递归）

    重点：

    交换指针，而不是交换数值

    1. class Solution(object):
    2.     def invertTree(self, root):
    3.         """
    4.         :type root: TreeNode
    5.         :rtype: TreeNode
    6.         """
    7.         if root is None:
    8.             return None
    9.         #前序遍历 
    10.         #交换左右节点
    11.         root.left,root.right = root.right,root.left
    12.         #遍历左节点
    13.         self.invertTree(root.left)
    14.         #遍历右节点
    15.         self.invertTree(root.right)
    16.         return root
    17.  
    18.         if root is None:
    19.             return None
    20.         #后序遍历 
    21.         
    22.         #遍历左节点
    23.         self.invertTree(root.left)
    24.         #遍历右节点
    25.         self.invertTree(root.right)
    26.         #交换左右节点
    27.         root.left,root.right = root.right,root.left
    28.         return root   
    29.         
    30.         if root is None:
    31.             return None
    32.         #中序遍历
    33.         #遍历左节点
    34.         self.invertTree(root.left)
    35.         #交换左右节点
    36.         root.left,root.right = root.right,root.left
    37.         #反转过后，右节点变左节点了，所以还得再次遍历左节点
    38.         #遍历右节点
    39.         self.invertTree(root.left)
    40.         return root

    重点：

    应该用什么遍历方式：前序，后序（优先使用）/中序（比较麻烦）

    递归三要素：

    • 确定参数和返回值
    • 确定终止条件
    • 明白处理逻辑

    题目链接/文章讲解/视频讲解：代码随想录

    二刷：未ac

    迭代法处理前序遍历。广度优先算法。层序遍历，我这使用的是。

    1. class Solution:
    2.     def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
    3.         if not root:
    4.             return root
    5.         que = deque()
    6.         que.append(root)
    7.         while len(que) != 0:
    8.             size = len(que)
    9.             while size > 0:
    10.                 node = que.popleft()
    11.                 node.left,node.right = node.right,node.left
    12.                 if node.left:
    13.                     que.append(node.left)
    14.                 if node.right:
    15.                     que.append(node.right)
    16.                 size -= 1
    17.         return root

    深度优先算法的前序遍历，要用栈！不能用队列，很容易有歧义的

    1. class Solution:
    2.     def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
    3.         if not root:
    4.             return root
    5.         st = deque()
    6.         st.append(root)
    7.         while st:
    8.             node = st.popleft()
    9.             node.left, node.right = node.right, node.left #中
    10.             
    11.             if node.left:
    12.                 st.append(node.left) #左
    13.             if node.right:
    14.                 st.append(node.right) #右
    15.         return root

    这里是深度优先算法的一个文档。得认真阅读。全忘记了

    前序

    1. class Solution:
    2.     def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
    3.         if not root:
    4.             return root
    5.         #深度优先算法,前序遍历，递归法
    6.         stack = []
    7.         stack.append(root)
    8.         while stack:
    9.             node = stack.pop()
    10.             #中
    11.             node.left,node.right = node.right,node.left
    12.             #右
    13.             if node.right:
    14.                 stack.append(node.right)
    15.             #左
    16.             if node.left:
    17.                 stack.append(node.left)
    18.         return root

    代码随想录

    三刷

    1. var invertTree = function(root) {
    2.     //我们先定义节点交换函数
    3.     const invertNode = function(root, left, right) {
    4.         let temp = left;
    5.         left = right;
    6.         right = temp;
    7.         root.left = left;
    8.         root.right = right;
    9.     }
    10.     //使用层序遍历
    11.     let queue = [];
    12.     if(root === null) {
    13.         return root;
    14.     } 
    15.     queue.push(root);
    16.     while(queue.length) {
    17.         let length = queue.length;
    18.         while(length--) {
    19.             let node = queue.shift();
    20.             //节点处理逻辑
    21.             invertNode(node, node.left, node.right);
    22.             node.left && queue.push(node.left);
    23.             node.right && queue.push(node.right);
    24.         }
    25.     }
    26.     return root;
    27. };

    101. 对称二叉树 （优先掌握递归） 

    1. class Solution(object):
    2.     def isSymmetric(self, root):
    3.         """
    4.         :type root: TreeNode
    5.         :rtype: bool
    6.         """
    7.         if not root:
    8.             return True
    9.         return self.recursion(root.left,root.right)
    10.         #本题需要判断，根节点的左右节点是否可以反转
    11.     def recursion(self,left,right):
    12.         #终止条件
    13.         if left is None and right is not None:return False
    14.         elif left is not None and right is None:return False
    15.         elif left is None and right is None:return True
    16.         elif left.val != right.val:return False
    17.         outside = self.recursion(left.left, right.right)
    18.         inside = self.recursion(left.right, right.left)
    19.         issame =  outside and inside
    20.         return issame

    重点：

    这道题考察的是判断根节点的左子树和右子树是否可以反转。（先比较外侧，再比较内侧，如果都相同，那么可以翻转）

    二叉树主要考察的是如何去遍历：这道题主要使用的是前序遍历或者后序遍历。

    题目链接/文章讲解/视频讲解：代码随想录

    三刷

    1. var isSymmetric = function(root) {
    2.     const recursion = function(left,right){
    3.         if(left === null && right !==null){
    4.             return false
    5.         }else if(left !== null && right === null){
    6.             return false
    7.         }else if(left === null && right === null){
    8.             return true
    9.         }else if(left.val !== right.val){
    10.             return false
    11.         }
    12.         let outside = recursion(left.left,right.right)
    13.         let inside = recursion(left.right,right.left)
    14.         let isSame = outside && inside
    15.         return isSame
    16.     }
    17.     return recursion(root.left,root.right)
    18.  
    19.     
    20. };

    100相同的树

    1. class Solution:
    2.     def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
    3.         #递归遍历
    4.         #参数返回值
    5.         #单层便利
    6.         #终止条件
    7.         def reversion(a,b):
    8.             if a is None and b is None:
    9.                 return True
    10.             elif a is not None and b is None:return False
    11.             elif a is None and b is not None:return False
    12.             elif a is not None and b is not None and a.val != b.val:return False
    13.             #反转
    14.             outside = reversion(a.left,b.left)
    15.             inside = reversion(a.right,b.right)
    16.             issame = outside and inside
    17.             return issame
    18.  
    19.         #如果两棵树都为空值的话    
    20.         if not p and not q:
    21.             return True
    22.         return reversion(p,q)

    三刷

    1. var isSameTree = function(p, q) {
    2.     const recursion = function(node1,node2){
    3.         if(node1 === null && node2 !==null){
    4.             return false
    5.         }else if(node1 !== null && node2 === null){
    6.             return false
    7.         }else if(node1 === null && node2 === null){
    8.             return true
    9.         }else if(node1.val !== node2.val){
    10.             return false
    11.         }
    12.         let oneSide = recursion(node1.left,node2.left)
    13.         let secSide = recursion(node1.right,node2.right)
    14.         let isSame = oneSide && secSide
    15.         return isSame
    16.     }
    17.     return recursion(p,q)
    18. };
    ​​​​​​​
    • 572.另一个树的子树
    1. class Solution:
    2.     def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
    3.         #递归法
    4.         def recursion(root,subroot):
    5.             if root is None and subroot is None:
    6.                 return True
    7.             elif root is not None and subroot is None:return False
    8.             elif root is None and subroot is not None:return False
    9.             elif root is not None and subroot is not None and root.val != subroot.val:return False
    10.             left = recursion(root.left,subroot.left)
    11.             right = recursion(root.right,subroot.right)
    12.             issame = left and right
    13.             return issame
    14.         def dfs(root,subroot):
    15.             #终止条件,因为是一直在移动root的，所以只用判断他是不是为空，如果是空，遍历完毕，返回false
    16.             if root is None:
    17.                 return False
    18.             if root.val == subroot.val and recursion(root,subroot):
    19.                 return True
    20.             return dfs(root.left,subroot) or dfs(root.right,subroot)
    21.         if not root and not subroot:
    22.             return True
    23.         return dfs(root,subRoot)

    二刷：未ac

    使用队列的写法

    1. class Solution:
    2.     def isSymmetric(self, root: Optional[TreeNode]) -> bool:
    3.         if root is None:
    4.             return True
    5.         que = deque()
    6.         que.append(root.left)
    7.         que.append(root.right)
    8.         while que:
    9.             leftnode = que.popleft()
    10.             rightnode = que.popleft()
    11.             if leftnode is None and rightnode is None:continue
    12.             if leftnode is not None and rightnode is None:return False
    13.             elif leftnode is None and rightnode is not None:return False
    14.             elif leftnode is not None and rightnode is not None and leftnode.val != rightnode.val:return False
    15.             #反转,将左边的右节点放入，
    16.             que.append(leftnode.left)
    17.             que.append(rightnode.right)
    18.             que.append(leftnode.right)
    19.             que.append(rightnode.left)
    20.         return True

    三刷

    1. var isSubtree = function(root, subRoot) {
    2.     // 现遍历到相同的树再进行判断
    3.     const recursion = function(node1,node2){
    4.         if(node1 === null && node2 === null){
    5.         return true
    6.         }else if(node1 === null || node2 === null){
    7.             return false
    8.         }else if(node1.val !== node2.val){
    9.             return false
    10.         }
    11.         let oneSide = recursion(node1.left,node2.left)
    12.         let secSide = recursion(node1.right,node2.right)
    13.         let isSame = oneSide && secSide
    14.         return isSame
    15.     }
    16.     const dfs = (node) => {
    17.         if (!node) return false;
    18.         if (recursion(node, subRoot)) return true;
    19.         return dfs(node.left) || dfs(node.right);
    20.     }
    21.     return dfs(root);
    22. };

  • 相关阅读:
    基于C++和QT实现的二进制数独游戏求解
    SLF4J 报错解决：No SLF4J providers were found
    设计模式——单例模式8种实现
    访问者模式
    Oracle EBS form开发 提示 FRM-15500:Valid and unique object name must be entered
    GPT实战系列-P-Tuning本地化训练ChatGLM2等LLM模型，到底做了什么？(一)
    独立站新手卖家应注意的要点
    分布式之业务高可用
    《 Python List 列表全实例详解系列（六）》__查找元素
    深度学习中的函数（一）
  • 原文地址：https://blog.csdn.net/weixin_42173016/article/details/127773588