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

2023-12-15 12:26:17

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

题目

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

示例 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 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3:
输入:root = [1,2], p = 1, q = 2
输出:1

提示:
树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。

思路

一开始我是想着正常递归遍历,然后记录一下搜索路径,然后遇到p或者q就记录找到了(flag=true)然后一直回退就完了。但是需要注意递归结束要remove的,否则记录的是递归顺序而不是从根节点到当前的搜索顺序。remove前的if(flag)也很重要,这表示找到了,就别remove了。然后对比p和q的路径就完了。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    boolean flag = false;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> pList = new ArrayList<TreeNode>();
        List<TreeNode> qList = new ArrayList<TreeNode>();
        dfs(root, pList, p);
        flag = false;
        dfs(root, qList, q);
        TreeNode res = new TreeNode();
        for (int i=0;i<Math.min(pList.size(), qList.size());i++) {
            if (pList.get(i) == qList.get(i)) {res = pList.get(i);}
            else {break;}
        }
        return res;
    }
    public void dfs(TreeNode root, List<TreeNode> list, TreeNode node) {
        if (flag || root == null) {
            list.add(null);
            return;
        }
        list.add(root);
        if (root == node) {
            flag = true;
            return;
        }
        dfs(root.left, list, node);
        if (flag) {return;}
        list.remove(list.size() - 1);
        dfs(root.right, list, node);
        if (flag) {return;}
        list.remove(list.size() - 1);
    }
}

在这里插入图片描述
但这个结果太拉了,其实是有更好的方法的。那就是p和q往上递归搜索,找到同一个节点就结束了。其实这就是后续遍历的用处,左右中。
这里我们来聊聊递归的写法细节,首先肯定我们知道是先写一个判断递归中止的函数。那其他的呢有没有返回值怎么判断,这里可以告诉大家:
1 如果需要搜索整棵二叉树且不用处理递归返回值,递归函数就不要返回值。
2 如果需要搜索整棵二叉树且需要处理递归返回值,递归函数就需要返回值。
3 如果要搜索其中一条符合条件的路径,那么递归一定需要返回值,因为遇到符合条件的路径了就要及时返回。
2的写法是

if (递归函数(root->left)) return ;
if (递归函数(root->right)) return ;

3的写法是

left = 递归函数(root->left);  // 左
right = 递归函数(root->right); // 右
left与right的逻辑处理;         // 中 

在递归函数有返回值的情况下:如果要搜索一条边,递归函数返回值不为空的时候,立刻返回,如果搜索整个树,直接用一个变量left、right接住返回值,这个left、right后序还有逻辑处理的需要,也就是后序遍历中处理中间节点的逻辑(也是回溯)。

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == p || root == q || root == null) {return root;}
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) {return root;}
        else if (left == null) {return right;}
        else if (right == null) {return left;}
        else {return null;}
    }
}

文章来源:https://blog.csdn.net/pige666/article/details/135010881
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。