二叉树的最近公共祖先

╰+攻爆jí腚メ 2021-06-22 15:38 361阅读 0赞

//给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。  
//  
// 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（  
//一个节点也可以是它自己的祖先）。”  
//  
// 例如，给定如下二叉树: root = \[3,5,1,6,2,0,8,null,null,7,4\]  
//  
// 示例 1:  
//  
// 输入: root = \[3,5,1,6,2,0,8,null,null,7,4\], p = 5, q = 1  
//输出: 3  
//解释: 节点 5 和节点 1 的最近公共祖先是节点 3。  
//  
// 示例 2:  
//  
// 输入: root = \[3,5,1,6,2,0,8,null,null,7,4\], p = 5, q = 4  
//输出: 5  
//解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。  
//  
// 说明:  
//  
// 所有节点的值都是唯一的。  
// p、q 为不同节点且均存在于给定的二叉树中。  
//  
// Related Topics 树

//leetcode submit region begin(Prohibit modification and deletion)  
/\*\*  
Definition for a binary tree node.  
public class TreeNode \{  
int val;  
TreeNode left;  
TreeNode right;  
TreeNode(int x) \{ val = x; \}  
\}  
\*/

*  思路1：  
    如果能打印出两个节点到根节点的路径，那么我们可以根据路径的重合节点，找到他们的公共父节点。  
    前提：我们能够找到路径，能找到路径就要能找到父节点，需要parent指针，但一般是没有的，就如本题。
 *  思路2：  
    采用递归的思想。先看代码，再解释。

class Solution { 
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 
            if (root == null || root == q || root == p) return root;
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            return left == null ? right : right == null ? left : root;
        }
    }

方法的入参是树根节点，需要找最近公共祖先的两个节点p和q。  
思想是对树进行深度遍历，如果在当前的子树根节点的左右子树分别能找到p、q的话（左还是右不影响），说明当前的子树根节点就是 最近公共祖先，如果在左子树找到p或q，右子树找不到p或q的话，说明p、q在左子树，反之在都在右子树。

难就难在递归需要我们逆向思维，先从左子树深度遍历走到底，然后一步一步弹栈，去右子树找。