题目：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“对于有根树 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; } * } */ //递归寻找p,q的公共祖先，因为p,q的公共祖先要么为root,要么为p或q本身。 当为root时，p,q必定为为root的左右 子树。我们这里第一次递归先对根节点“root”的左右子树进行遍历，后续递归遍历中每个节点分别充当root根节 点，对整个二叉树遍历一遍，必定可以找到p,q的公共祖先。 class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { //root=root.left ，root.right=root 递归中root依次为传入的左子节点与右子节点 if(root==null) return null; //递归终止条件,跨过叶节点（到达最底层） if(root == p||root == q) return root; //左右子树依次遍历，如果遍历到了p,或q,迭代终止，依次进行返回。 TreeNode left = lowestCommonAncestor(root.left, p, q); //对左子树进行递归遍历，查看是否能找到p或q。找到了就赋给left TreeNode right = lowestCommonAncestor(root.right, p, q); //对右子树递归遍历,查看是否能找到p或q,找到了就赋给right 。 //上面整个过程是后续遍历，从下到上依次迭代 if(left == null){ //左子树为空，说明在左子树没找到p或q。p,q都在右子树，此时右子树必定为他们的最近公共祖先 return right; } if(right == null){ //右子树为空说明在右子树没找到p或q。p,q都在左子树，此时左子树为他们的最近公共祖先 return left; } //左右都不为空，此时p，q必定在同一层，因为left与right在每层迭代中存放的要么是p或q， 要么是null,此时两个都不为null,那么p，q必定在同一层,它的父子节点root就是最近的公共祖先 if(left != null && right != null){ return root; } return null;//遍历完整个二叉树都为找到p,q则返回空 } }