点击关注公众号，干货第一时间送达
这道题可算来了！
二叉树的最近公共祖先，
算是二叉树系列问题中，比较经典的一题了。
需要诸位动动小脑瓜，灵活地想一想，就可以的。
老样子，咱们先审题！
一、各位，请听题
寥寥几字，
那肯定就不简单了
至于，什么是最近公共祖先呢？看下面。
节点3，就是节点6和节点8的最近公共祖先。
当然，也可能是两个节点中的一个节点，就是他们两个的最近公共祖先：
节点2和节点4，最近公共祖先就是节点2。
咋整啊？
用后序遍历！
二、解题
因为需要求两个节点的祖先，是要从下往上判断的。
从下往上？
是不是和后序遍历很像？
对！就是的！
我们先判断左孩子（左子树），再判断右孩子（右子树），
判断条件是：当前这个孩子节点是否为null，或者恰好的等于给定的两个节点 p q
直接看代码！
完整代码：
public class CodingDemo {
private static class TreeNode{
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
/**
* TODO: 二叉树的最近公共祖先
* @param root
* @param p
* @param q
* @return
*/
public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//1，basecase
if (root == null || root == p || root == q){
return root;
}
//2，后序遍历，所以先操作左子树，右子树，
//当递归序返回到当前节点时，再操作当前节点
TreeNode leftSubTree = lowestCommonAncestor(root.left, p, q);//左子树中是否有 p q 节点
TreeNode rightSubTree = lowestCommonAncestor(root.right, p, q);//右子树中是否有 p q 节点
//3, 如果左右子树中都有 p q，则说明当前节点，就是 p q的最近公共祖先
if (leftSubTree != null && rightSubTree != null){
return root;//返回当前节点
}
//4,否则，往有 p q 节点的子树进行延伸
return leftSubTree != null ? leftSubTree : rightSubTree;
}
public static void main(String[] args) {
TreeNode node1 = new TreeNode(1);
TreeNode node2 = new TreeNode(2);
TreeNode node3 = new TreeNode(3);
TreeNode node4 = new TreeNode(4);
TreeNode node5 = new TreeNode(5);
TreeNode node6 = new TreeNode(6);
TreeNode node7 = new TreeNode(7);
TreeNode node8 = new TreeNode(8);
node1.left = node2;
node1.left.left = node4;
node1.left.right = node5;
node1.right = node3;
node1.right.left = node6;
node1.right.right = node7;
node1.right.right.left = node8;
System.out.println(lowestCommonAncestor(node1, node6, node8).val);
}
}
输出：
D:\java\bin\java.exe
3
文章转载自皮皮克克，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
