本文共 540 字,大约阅读时间需要 1 分钟。
找出两个节点的公共祖先,树是普通二叉树
lowestCommonAncestor找在root为根节点的子树上遍历到的第一个p或者q,如果两个都遍历到就返回root,如果p和q都不在这个子树上就返回null,否则返回p和q里面先遍历到的那个。因此如果left和right都不是null,那么就返回root
public 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); return left == null ? right : right == null ? left : root; }}
转载地址:http://hahld.baihongyu.com/