236. 二叉树的最近公共祖先

题目链接:

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 }

 

上一篇:Flexbox


下一篇:LeetCode#236二叉树的最近公共祖先