一、目标

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。

二、代码解读

总体代码：

本题是寻找一个节点的最近公共祖先，一定选择的是后序遍历。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {//递归终止条件if(root == null){return null;}//如果遇到了p或者q就返回当前节点if(root == p || root == q){return root;}TreeNode left = lowestCommonAncestor(root.left, p, q);TreeNode right = lowestCommonAncestor(root.right, p, q);//分别处理不同情况if(left != null && right != null){return root;}if(left == null && right != null){return right;}if(left != null && right == null){return left;}return null;}
}

递归第一步：递归终止条件

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {//递归终止条件if(root == null){return null;}

递归第二步：确定单层逻辑

要选择后序遍历，每次要接住处理后返回的节点（或者是null），每次如果找到了p或者q，则return回当前节点，如果找不到就直到走到叶子节点时开始处理，处理逻辑为：

每次回溯的时候会判断是不是p或者q，是的话返回

如果左右当前节点左右都不为空，说明下面已经找到，直接return当前的root

如果左右有一个不为空，则返回那个不为空的

        if(root == p || root == q){return root;}TreeNode left = lowestCommonAncestor(root.left, p, q);TreeNode right = lowestCommonAncestor(root.right, p, q);//分别处理不同情况if(left != null && right != null){return root;}if(left == null && right != null){return right;}if(left != null && right == null){return left;}return null;

三、总结

本题设计回溯，值得深思