题目链接:
https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
解题思路:
递归看起来是从上往下,实际上从下往上的。如果发现在左右子树一个为空,一个不为空,就证明在那个不为空的子树。我们不需要关心p和q到底返回的是具体哪个,只需要知道左右不为空就行
有三种情况,p q 都在左子树或右子树,p q分别在左子树和右子树,
判断当前遍历的节点是否为空,为空返回null,节点是否等于p,是否等于q,是的话返回null。
之后判断left 和right是否为空, 若都不为空 ,则当前root为答案,若其中一个为空,则返回另一边,为答案。
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */ 10 class Solution { 11 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 12 if(root==null || root==p||root==q) 13 return root; 14 TreeNode left = lowestCommonAncestor(root.left,p,q); 15 TreeNode right = lowestCommonAncestor(root.right,p,q); 16 if(left!=null && right!=null) 17 return root; 18 if(left==null) 19 return right; 20 return left; 21 } 22 }