深圳网站制作费用电子商务网站建设有什么意义

深圳网站制作费用,电子商务网站建设有什么意义,杂志社网站模板,高端ppt制作题目#xff1a;思路#xff1a;递归遍历#xff1a;从根节点出发#xff0c;递归遍历左、右子树#xff0c;目标是找到 p 或 q#xff1b;回溯 “判断”—— 确定 LCA#xff1a;递归遍历完左右子树后#xff0c;会得到两个结果#xff08;left#xff1a;左子树找到…题目思路递归遍历从根节点出发递归遍历左、右子树目标是找到p或q回溯 “判断”—— 确定 LCA递归遍历完左右子树后会得到两个结果left左子树找到的节点right右子树找到的节点通过这两个结果判断当前节点的角色左右子树结果含义p/q的位置当前节点的角色返回值leftNone rightNone既不在左子树也不在右子树无目标无贡献NoneleftNone right≠None都在右子树右子树已找到目标 / LCA传递右子树的结果rightleft≠None rightNone都在左子树左子树已找到目标 / LCA传递左子树的结果leftleft≠None right≠None分别在左、右子树跨子树自身就是最近公共祖先当前节点root3.最终回溯 —— 定位最深 LCA递归会从叶子节点向上回溯每一层都按上述规则判断若p/q都在某一子树中结果会持续向上传递该子树的 LCA若p/q分属左右子树当前节点就是 “最深” 的公共祖先因为再往下的子树只能找到其中一个目标。代码# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val x # self.left None # self.right None class Solution: def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode: //只要当前根节点是p和q中的任意一个就返回因为不能比这个更深了再深p和q中的一个就没了 if not root or root p or root q: return root //根节点不是p和q中的任意一个那么就继续分别往左子树和右子树找p和q left self.lowestCommonAncestor(root.left,p,q) right self.lowestCommonAncestor(root.right,p,q) //p和q都没找到那就没有 if not left and not right: return None //左子树没有p也没有q就返回右子树的结果 if not left: return right //右子树没有p也没有q就返回左子树的结果 if not right: return left //左右子树都找到p和q了那就说明p和q分别在左右两个子树上所以此时的最近公共祖先就是root return root