• leetcode-二叉树的最近公共祖先-递归


    leetcode

    在这里插入图片描述

    思路一 递归

    我的第一想法就是判断p,q是否在root的同一侧子树上, 具体决策步骤就是:
    1 . 如果root==p,则p就是p,q的最近公共祖先。
    2 . 如果root==q,则q就是p,q的最近公共祖先。
    3 . 如果p,q分别在root的两侧的子树上,则root就是p,q的最近公共祖先。
    4 . 如果p,q都在root的同一侧子树上,比如都在root的左子树上,就可以运用递归思想,令root为当前root节点的左孩子节点,依然进行上述分析,分析的问题其实没有变,只是数据规模变小了。直至1或2或3中的条件满足就递归结束。

    我们需要定义一个函数,表示节点p是否在节点node的左子树上boolean isOnLeftChildTree(TreeNode node, TreeNode p)

    定义一个函数,表示节点p是否在节点node的右子树上boolean isOnRightChildTree(TreeNode node, TreeNode p)

    定义一个函数,表示节点p是否是节点node的子孙(node与p相等时也算子孙)boolean isChildren(TreeNode node, TreeNode p)

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            return lowestCommonAncestor1(root, p, q);
        }
    
        public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
            if (root == p){
                return p;
            }
            if (root == q){
                return q;
            }
            if (isOnLeftChildTree(root, p) && isOnLeftChildTree(root, q)){
                return lowestCommonAncestor1(root.left, p, q);
            }
    
            if (isOnRightChildTree(root, p) && isOnRightChildTree(root, q)){
                return lowestCommonAncestor1(root.right, p, q);
            }
            return root;
        }
    
        /**
         * 判断p是否在node的左子树上
         * @param node
         * @param p
         * @return
         */
        private boolean isOnLeftChildTree(TreeNode node, TreeNode p){
            if (node == null){
                return false;
            }
            if (node == p){
                return false;
            }
            return isChildren(node.left, p);
        }
    
        private boolean isOnRightChildTree(TreeNode node, TreeNode p){
            if (node == null){
                return false;
            }
            if (node == p){
                return false;
            }
            return isChildren(node.right, p);
        }
    
        /**
         * 判断p是否是node的子孙(node==p时,也算是其子孙)
         * @param node
         * @param p
         * @return
         */
        private boolean isChildren(TreeNode node, TreeNode p){
            if (node == null){
                return false;
            }
            if (node == p){
                return true;
            }
    
            return isChildren(node.left, p) || isChildren(node.right, p);
        }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63

    思路2 递归优化,使用栈

    上述分析是ok的,但是时间成本较高,递归的过程中,总要找到节点p或者找遍所有节点才知道p是否在当前节点的左(右)子树中。我们可以只找到p一次就可以,记录下从p返回根节点的路径stackP。同理,只找到q一次,记录下从q返回根节点的路径StackQ。

    每次都从stackP和stackQ分别弹出一个元素,直至弹出的元素不再相同,则上一个弹出的元素(是相同的)就是最近公共祖先。

    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
            Stack<TreeNode> stackP = new Stack<>();
            findChild(root, p, stackP);
    
            Stack<TreeNode> stackQ = new Stack<>();
            findChild(root, q, stackQ);
            TreeNode lastSameTreeNode = root;
            while (!stackP.isEmpty() && !stackQ.isEmpty()){
                TreeNode popP = stackP.pop();
                TreeNode popQ = stackQ.pop();
                if (popP == popQ){
                    lastSameTreeNode = popP;
                }
            }
            return lastSameTreeNode;
        }
    
        /**
         * 从parent向下递归寻找,是否可以遍历到child,如果可以,再跳出递归的过程中记录下child到parent的路径
         *
         * @param parent
         * @param child
         * @param stack
         * @return
         */
        public boolean findChild(TreeNode parent, TreeNode child, Stack<TreeNode> stack) {
            if (child == parent) {
                stack.push(child);
                return true;
            }
            if (parent == null) {
                return false;
            }
            if (findChild(parent.left, child, stack)) {
                stack.push(parent);
                return true;
            }
            if (findChild(parent.right, child, stack)) {
                stack.push(parent);
                return true;
            }
            return false;
        }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
  • 相关阅读:
    <硬件设计>运放+三极管组成的恒流源VI电路设计与分析
    Mindspore-Tensor条件索引及赋值如何实现?
    JavaScript实现快速排序
    【软件设计师】(一) 计算机系统 笔记总结
    After Effects动态图形和数据可视化
    Tools_Download
    空城机在CSDN的四周年创作纪念日
    如何戒掉短视频?2个方法适合职场人,从未失败过
    C#实现根据字体名称获取字体文件名
    Java.lang.Class类 getSupperclass()方法有什么功能呢?
  • 原文地址:https://blog.csdn.net/gs_albb/article/details/125494243