leetcode刷题记录 二叉树的最近公共祖先

leetcode 二叉树的最近公共祖先

解题思路： 根据以上定义，若 rootroot 是 p, qp,q 的 最近公共祖先 ，则只可能为以下情况之一：

p和 q在 root的子树中，且分列 root的 异侧（即分别在左、右子树中）；p = root，且q在root的左或右子树中；q = root，且p在root的左或右子树中；

考虑通过递归对二叉树进行后序遍历，当遇到节点 p 或 q 时返回。从底至顶回溯，当节点 p, q 在节点 root 的异侧时，节点 root即为最近公共祖先，则向上返回 root 。

代码如下：

class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root == null || root == p || root == q)return root; //后序遍历 TreeNode left = lowestCommonAncestor(root.left,p,q); TreeNode right = lowestCommonAncestor(root.right,p,q); if(left == null) return right; if(right == null) return left; return root; } }