二叉树的最近公共祖先
题目链接: https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree
解题思路:
最近公共祖先有两种情况
当前节点
p
或q
为其中之一p或q归属于同一个棵子树
从
root
开始遍历树,判断当前节点的值是否与p
或q
相等,若相等则返回当前节点,若不相等,则从左右子树中查找若左右子树中各自查找到
p
或q
,则说明当前节点为最近公共祖先若左子树中未查找到
p
或q
,则说明p
为q
的最近公共祖先或q
为p
的最近公共祖先,返回从子树中查找到的子节点
复杂度分析
最后更新于