计算机软件网站建设,唐山网站建设500元,免费ppt课件下载网站,网页设计代码步骤题目 思路 解题的关键是知道自顶向低递归遍历#xff0c;第一次遇到root在p和q的区间中时#xff0c;则root就是p和q的最近公共祖先节点。
递归法
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val x
# … 题目 思路 解题的关键是知道自顶向低递归遍历第一次遇到root在p和q的区间中时则root就是p和q的最近公共祖先节点。
递归法
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val x
# self.left None
# self.right Noneclass Solution:def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode:if not root:return if root.valp.val and root.valq.val:left self.lowestCommonAncestor(root.left, p, q)if left:return leftif root.valp.val and root.valq.val:right self.lowestCommonAncestor(root.right, p, q)if right:return rightreturn root
迭代法
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val x
# self.left None
# self.right Noneclass Solution:def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode:while root:if root.valp.val and root.valq.val:root root.leftelif root.valp.val and root.valq.val:root root.rightelse:return root
