ps做网站如何,专业邯郸网站建设,长沙网站排名提升,农业行业网站建设基础知识补充 完全二叉树#xff1a;顺序存储#xff08;数组#xff09; 非根节点的父节点序号floor((i-1)/2) 序号i的左孩子节点序号2*i1 右孩子节点序号2*i2 一般二叉树#xff1a;链式存储 结构#xff1a;left指针指向左子节点#xff0c;right指针指向右子节点顺序存储数组 非根节点的父节点序号floor((i-1)/2) 序号i的左孩子节点序号2*i1 右孩子节点序号2*i2 一般二叉树链式存储 结构left指针指向左子节点right指针指向右子节点data存储数据项 class TreeNode(object): def __init__(self, data, leftNone, rightNone): self.data data self.left left self.right right 平衡二叉树左子树和右子树的高度之差的绝对值不超过1且左子树和右子树也是平衡二叉树 二叉搜索树左子树上所有节点的值都小于根节点的值右子树上所有节点的值都大于根节点的值且左子树和右子树也是二叉搜索树 基础操作补充 1. 二叉树的插入 先判断父节点是否存在再判断左子节点是否存在构建右子节点后需要弹出父节点 class BinTree():def _init__(self):self.root None self.ls []def add(self,data):node TreeNode(data)if self.root None:self.root nodeself.ls.append(self.root)else:rootNode self.ls[0]if rootNode.left None:rootNode.left nodeself.ls.append(rootNode.left)elif rootNode.right None:rootNode.right nodeself.ls.append(rootNode.right)self.ls.pop(0) #弹出子树已满的节点 2. 二叉树的遍历 前序遍历深度优先当前节点-当前节点的左子树-当前节点的右子树 递归或栈实现 中序遍历深度优先当前节点的左子树-当前节点-当前节点的右子树 递归或栈实现 后序遍历深度优先当前节点的左子树-当前节点的右子树-当前节点 递归或栈实现 层序遍历广度优先各层级中从左到右的遍历 队列实现 已知两种二叉树遍历序列其中需要包括中序遍历可以唯一确定一棵二叉树 #前序遍历的递归实现 def preOrderTraversal(self,root): if root None: returnprint(root.data)self.preOrderTraversal(root.left)self.preOrderTraversal(root.right)#前序遍历的栈实现def preOrderStack(self,root): if root None:returnstack [] #存放节点result [] #存放节点值node rootwhile node or stack:while node: result.append(node.data)stack.append(node)node node.leftnode stack.pop()node node.rightprint(result)#中序遍历的递归实现def inOrderTraversal(self,root): if root None: returnself.preOrderTraversal(root.left)print(root.data)self.preOrderTraversal(root.right)#中序遍历的栈实现def inOrderStack(self,root): if root None:returnstack [] #存放节点result [] #存放节点值node rootwhile node or stack:while node: stack.append(node)node node.leftnode stack.pop()result.append(node.data)node node.rightprint(result)#后序遍历的递归实现def postOrderTraversal(self,root): if root None: returnself.preOrderTraversal(root.left)self.preOrderTraversal(root.right)print(root.data)#后序遍历的栈实现def inOrderStack(self,root): if root None:returnstack [] #存放节点result [] #存放节点值seq []node rootwhile node or stack: #左-右-根视为根-右-左前序的左右互换的逆序while node: seq.append(node.data) stack.append(node)node node.right #内外层左右互换node stack.pop()node node.leftwhile seq:result.append(seq.pop()) #逆序print(result)#层序遍历的队列实现def levelOrder(seLf, root): if root None:returnqueue []result []node rootqueue.append(node)while queue:node queue.pop(0)result.append(node.data)if node.left ! None:queue.append(node.left)if node.right ! None:queue.append(node.right)print(result) 题目
94 二叉树的中序遍历
给定一个二叉树的根节点 root 返回 它的 中序 遍历 。 方法一递归实现 方法二栈实现 class Solution(object):def inorderTraversal(self, root)::type root: TreeNode:rtype: List[int]if root None: returnstack []result []node rootwhile node or stack:while node:stack.append(node)node node.leftnode stack.pop()result.append(node.val)node node.rightreturn result 方法三颜色标记法给每个节点一个访问状态未访问为白已访问为黑 中序出栈顺序左-中-右 对应的入栈顺序右-中-左 栈先进后出 class Solution(object):def inorderTraversal(self, root)::type root: TreeNode:rtype: List[int]white, black 0, 1result []stack [(white, root)]while stack: color, node stack.pop()if node is None:continueif color white:stack.append((white, node.right))stack.append((black, node))stack.append((white, node.left)) # 适用于前中后序遍历改变这里位置即可else:result.append(node.val)return result 方法四莫里斯遍历 思路如果左节点不为空就将当前节点和右子树全部挂在左子树的最右子树下 如果左节点为空打印节点并向右遍历 class Solution(object):def inorderTraversal(self, root)::type root: TreeNode:rtype: List[int]res []pre Nonewhile root:# 如果左节点不为空就将当前节点连带右子树全部挂到左节点的最右子树下面if root.left:pre root.leftwhile pre.right:pre pre.rightpre.right root tmp root root root.left # 切换到左子树的父节点tmp.left None # 取消当前节点到左子树的链接# 左子树为空则打印这个节点并向右边遍历 else:res.append(root.val)root root.rightreturn res 104 二叉树的最大深度
给定一个二叉树 root 返回其最大深度。 方法一二叉树最大深度 max(左子树高度 右子树高度)1 class Solution(object):def maxDepth(self, root)::type root: TreeNode:rtype: intif 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 方法二用临时队列维护每层节点一层结束后将深度1 class Solution:def maxDepth(self, root):if not root: return 0queue, res [root], 0while queue:tmp []for node in queue:if node.left: tmp.append(node.left)if node.right: tmp.append(node.right)queue tmpres 1return res226 翻转二叉树
给你一棵二叉树的根节点 root 翻转这棵二叉树并返回其根节点。 方法一用栈做中序遍历 class Solution(object):def invertTree(self, root)::type root: TreeNode:rtype: TreeNodestack []node rootwhile node or stack:while node:stack.append(node)node node.leftnode stack.pop()node.left, node.right node.right, node.leftnode node.leftreturn root 方法二用队列做层级遍历 class Solution(object):def invertTree(self, root)::type root: TreeNode:rtype: TreeNodeif root is None:returnqueue [root]while queue:tmp queue.pop(0)tmp.left,tmp.right tmp.right,tmp.leftif tmp.left:queue.append(tmp.left)if tmp.right:queue.append(tmp.right)return root 方法三递归实现 class Solution(object):def invertTree(self, root)::type root: TreeNode:rtype: TreeNodeif root is None: returnroot.left,root.right root.right,root.leftself.invertTree(root.left)self.invertTree(root.right) return root101 对称二叉树
给你一个二叉树的根节点 root 检查它是否轴对称。 方法一用队列做层级遍历判断每层节点是否对称 class Solution(object):def invertTree(self, root)::type root: TreeNode:rtype: TreeNodequece [root]while quece:tmp []val []for node in quece:if node.left:tmp.append(node.left)val.append(node.left.val)else:val.append(101) # 101是节点值范围之外的数if node.right:tmp.append(node.right)val.append(node.right.val)else:val.append(101)if val ! val[::-1]:return False # 耗时quece tmpreturn True # 不用滚动队列的话就一次性考虑两个节点并在放置时将需要比较的节点相邻放置
class Solution(object):def isSymmetric(self, root)::type root: TreeNode:rtype: boolif not root or not (root.left or root.right):return True queue [root.left,root.right]while queue:left queue.pop(0) right queue.pop(0)if not (left or right): # 两个节点都为空continueif not (left and right): # 两个节点中有一个为空return Falseif left.val!right.val: # 两个节点的值不相等return Falsequeue.append(left.left)queue.append(right.right)queue.append(left.right)queue.append(right.left)return True 方法二递归实现 class Solution(object):def isSymmetric(self, root)::type root: TreeNode:rtype: boolif not root: return Truedef dfs(left,right):if not (left or right): # 两个节点都为空return Trueif not (left and right): # 两个节点中有一个为空return Falseif left.val!right.val: # 两个节点的值不相等return Falsereturn dfs(left.left,right.right) and dfs(left.right,right.left)return dfs(root.left,root.right)543 二叉树的直径
给你一棵二叉树的根节点返回该树的 直径 。二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。两节点之间路径的 长度 由它们之间边数表示。 分析直径 左子树到父节点的最长路径 右子树到父节点的最长路径 左/右子树到父节点的最长路径 左/右子树深度 子树深度不用重复计算height max(左子树深度 右子树深度)1 方法一使用全局变量 class Solution(object):def diameterOfBinaryTree(self, root)::type root: TreeNode:rtype: intglobal maxx maxx 0def depth(root):if root is None:return 0left depth(root.left)right depth(root.right)global maxxmaxx max(maxx, leftright)return max(left, right)1depth(root)return maxx 方法二不使用全局变量 class Solution(object):def diameterOfBinaryTree(self, root)::type root: TreeNode:rtype: intdepth, length self.depth(root)return lengthdef depth(self, root):if root is None:return (0, 0)left_depth, left_length self.depth(root.left)right_depth, right_length self.depth(root.right)depth max(left_depth, right_depth) 1length max(left_length, right_length, left_depth right_depth)return depth, length 102 层序遍历
给你二叉树的根节点 root 返回其节点值的 层序遍历 。 即逐层地从左到右访问所有节点。 方法一两个数组实现 class Solution(object):def levelOrder(self, root)::type root: TreeNode:rtype: List[List[int]]if root is None:return []quece, result [root], []while quece: tmp_res, tmp_que [], [] while quece:node quece.pop(0)tmp_res.append(node.val)if node.left:tmp_que.append(node.left)if node.right:tmp_que.append(node.right)result.append(tmp_res)quece tmp_que return result 方法二一个数组实现用变量确定每层需要处理的子节点数即可正常插入数组 class Solution(object):def levelOrder(self, root)::type root: TreeNode:rtype: List[List[int]]if root is None:return []quece, result [root], []while quece: length len(quece) tmp_res [] for i in range(length):node quece.pop(0)tmp_res.append(node.val)if node.left:quece.append(node.left)if node.right:quece.append(node.right)result.append(tmp_res) return result 108 将有序数组转换为二叉搜索树
给你一个整数数组 nums 其中元素已经按 升序 排列请你将其转换为一棵平衡二叉搜索树。 针对平衡同时添加左子树和右子树针对搜索将数组确定父节点后进行二分 递归实现 class Solution(object):def sortedArrayToBST(self, nums)::type nums: List[int]:rtype: TreeNodedef balanceTree(left, right):if left right: return Nonemid (leftright)//2root TreeNode(nums[mid])root.left balanceTree(left, mid-1)root.right balanceTree(mid1, right)left, right 0, len(nums)-1return balanceTree(left, right) 98 验证二叉搜索树
给你一个二叉树的根节点 root 判断其是否是一个有效的二叉搜索树。 方法一验证左子节点值父节点值右子节点值 不够准确 在验证10的右子树时首先所有值要大于10即需要记录左右子树的不同边界值左子树-上界 右子树-下界 对于节点6来说先在右子树确定下界为10再在左子树确定上界为15而6不属于这个区间 class Solution(object):def isValidBST(self, root)::type root: TreeNode:rtype: booldef isBST(node, low, up):if node is None:return Trueif node.vallow or node.valup: return Falsereturn isBST(node.left,low,node.val) and isBST(node.right,node.val,up)return isBST(root, -2**31-1, 2**31) # 题目范围的边界值 方法二利用二叉搜索树的中序遍历一定升序排列性质 在构建中序遍历数组的同时可以进行升序比较 230 二叉搜索树中第K小的元素
给定一个二叉搜索树的根节点 root 和一个整数 k 请你设计一个算法查找其中第 k 个最小元素从 1 开始计数。 利用二叉搜索树的中序遍历一定升序排列性质构建中序遍历数组后直接取出第k个值即可不构建中序遍历数组的话也可以选择对k处理在需要插入值的位置将k减一k归零时对应输出 class Solution(object):def kthSmallest(self, root, k)::type root: TreeNode:type k: int:rtype: intstack []result []while root or stack:while root:stack.append(root)root root.leftroot stack.pop()result.append(root.val)root root.rightreturn result[k-1]class Solution:def kthSmallest(self, root, k):stack []while root or stack:while root:stack.append(root)root root.leftroot stack.pop()k - 1if k 0: return root.valroot root.right199 二叉树的右视图
给定一个二叉树的 根节点 root想象自己站在它的右侧按照从顶部到底部的顺序返回从右侧所能看到的节点值。 返回层序遍历数组每层的最后一个值 class Solution(object):def levelOrder(self, root)::type root: TreeNode:rtype: List[List[int]]if root is None:return []quece, result [root], []while quece: length len(quece) tmp_res [] for i in range(length):node quece.pop(0)tmp_res.append(node.val) # if i length-1: result.append(node.val) if node.left:quece.append(node.left)if node.right:quece.append(node.right)result.append(tmp_res[-1]) return result 114. 二叉树展开为链表
给你二叉树的根结点 root 请你将它展开为一个单链表
展开后的单链表应该同样使用 TreeNode 其中 right 子指针指向链表中下一个结点而左子指针始终为 null 。展开后的单链表应该与二叉树 先序遍历 顺序相同。 方法一颜色标记法出栈要求中-前-后入栈则是右-前-中 需要创建虚拟链表头结点 class Solution(object):def flatten(self, root)::type root: TreeNode:rtype: None Do not return anything, modify root in-place instead.white, black 0, 1stack [(white, root)]head TreeNode(0)pre_node headwhile stack:color, node stack.pop()if color white:if node.right:stack.append((white, node.right))if node.left:stack.append((white, node.left))stack.append((black, node))else:node.left Nonepre_node.right nodepre_node nodereturn head.right 方法二找到链表的前置节点 对于当前节点需要将其左子树的根节点移到右侧才能满足链表要求而其右子树的根节点在链表中需要接在左子树最右结点之后。 class Solution(object):def flatten(self, root)::type root: TreeNode:rtype: None Do not return anything, modify root in-place instead.node rootwhile node:if node.left:left_node left_last_node node.leftwhile left_last_node.right:left_last_node left_last_node.rightleft_last_node.right node.rightnode.left Nonenode.right left_nodenode node.rightreturn root 105 从前序与中序遍历序列构造二叉树
给定两个整数数组 preorder 和 inorder 其中 preorder 是二叉树的先序遍历 inorder 是同一棵树的中序遍历请构造二叉树并返回其根节点。 前序遍历中-左-右 中序遍历左-中-右 前序遍历的第一个元素为根节点在中序遍历序列找到根节点后就能将元素二分为左子树元素和右子树元素再在前序遍历序列中找到左子树的根节点和右子树的根节点... class Solution(object):def buildTree(self, preorder, inorder)::type preorder: List[int]:type inorder: List[int]:rtype: TreeNodedef bulidThree(preorder, inorder):if preorder:root TreeNode(preorder[0])idx inorder.index(preorder[0])inorder_left inorder[:idx]inorder_right inorder[idx1:]preorder_left preorder[1:idx1]preorder_right preorder[idx1:]root.left bulidThree(preorder_left, inorder_left)root.right bulidThree(preorder_right, inorder_right)return rootelse:returnreturn bulidThree(preorder, inorder) 每次查找根节点坐标会造成时间浪费可以用hashmap存储空间换时间 437 路径总和III
给定一个二叉树的根节点 root 和一个整数 targetSum 求该二叉树里节点值之和等于 targetSum 的 路径 的数目。路径 不需要从根节点开始也不需要在叶子节点结束但是路径方向必须是向下的只能从父节点到子节点。 统计从根节点出发到每个子节点的数值和用不同节点的数值和做差得到截选的路径类似前缀和想法 需要在退出当前节点时更新前缀和保证路径方向向下 class Solution(object):def pathSum(self, root, targetSum)::type root: TreeNode:type targetSum: int:rtype: intglobal outcur_sum, out 0, 0hash {0:1} # 初始化不然根节点与目标值相等时只能插入hashdef partSum(root, targetSum, hash, cur_sum):if root is None: return 0global outcur_sum root.valif targetSum - cur_sum in hash: out hash[targetSum-cur_sum]if cur_sum in hash:hash[cur_sum] 1 # 有正有负会出现重复的前缀和else:hash[cur_sum] 1partSum(root.left, targetSum, hash, cur_sum)partSum(root.right, targetSum, hash, cur_sum)hash[cur_sum] - 1cur_sum - root.valpartSum(root, targetSum, hash, cur_sum)return out 236 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。” 对于当前节点若能从其左子树中找到p/q并从其右子树中找到q/p则该节点为最近公共祖先节点 若左侧无p/q则pq均在右子树将当前节点切换到当前右子节点 终止条件切换到叶子节点或找到p/q class Solution(object):def lowestCommonAncestor(self, root, p, q)::type root: TreeNode:type p: TreeNode:type q: TreeNode:rtype: TreeNodeif rootp or rootq or rootNone: return rootleftself.lowestCommonAncestor(root.left,p,q)rightself.lowestCommonAncestor(root.right,p,q)if left and right:return rootif left and rightNone:return leftif right and leftNone:return right 124 二叉树的最大路径和
二叉树中的 路径 被定义为一条节点序列序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点且不一定经过根节点。路径和 是路径中各节点值的总和。给你一个二叉树的根节点 root 返回其 最大路径和 。 和543相似的思路只是不再记录深度而是路径和 class Solution(object):def maxPathSum(self, root)::type root: TreeNode:rtype: intglobal max_sum max_sum -1001 # 题目给出的节点的值的下界def partPathSum(root):if root is None:return 0left partPathSum(root.left)left max(left, 0) # 除去负值right partPathSum(root.right)right max(right, 0)global max_summax_sum max(max_sum, root.valleftright)return root.valmax(left, right)partPathSum(root)return max_sum
