本文共 1180 字，大约阅读时间需要 3 分钟。

假设有一个二叉树、根节点为TreeNode root、p节点和 q节点均在二叉树中、求p和q的最近公共祖先节点。

优雅的递归解法:

对于这个问题, 我们定义一个函数、但是这个函数扩充这个问题的定义

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)

 这个函数的扩充定义是什么呢？

虽然题目是保证p、q均在树中、但是我们为了实现递归解法、必须要考虑p、q有一个不在或者是均不在树中的情况来应对子树的情况。

扩充定义:

1、如果根节点为null、返回null

2、如果p在树中、q不在、该函数返回p; 如果p不在树中、q在、则返回q;

3、如果p、q均不在树中、返回null、

4、如果p、q均在树中、返回最近公共祖先。

至于为什么定义2是这样、完全是一种扩充自定义规则、也是一种巧妙地设计。

public class NearestCommonAncestor {    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {        if (root == null){            return null;        }        // 这一步的意思是:只要root节点和其中一个节点相等、那么即使另一个节点不在树中、也返回这个节点。        if(root == p || root == q) {            return root;        }        TreeNode lAns = lowestCommonAncestor(root.left, p, q);        if(lAns == null){            return lowestCommonAncestor(root.right, p, q);        }        TreeNode rAns = lowestCommonAncestor(root.right, p, q);        if(rAns == null){            return lAns;        }else{            return root;        }    }    static class TreeNode {        int val;        TreeNode left;        TreeNode right;        public TreeNode(int val){            this.val = val;        }    }}

转载地址：http://gnzji.baihongyu.com/