leetcode刷题(10)二叉树(4)

简介: leetcode刷题(10)二叉树(4)

二叉树的最近公共祖先

leetcode之二叉树的最近公共祖先(难度:中等)


题目要求

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


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


示例 1:

image.png

输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1

输出:3

解释:节点 5 和节点 1 的最近公共祖先是节点 3 。


示例 2:

35.png

输入: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

/**
 * 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) {
    }
}

做题思路

做这个题呢,我们有两种方法:


方法一

通过root根节点的移动在左子树和右子树中来找这两个节点,如果这两个节点分别在左子树和右子树中,我们就返回根节点,如果这两个节点都在左子树或者右子树,我们就返回那个深度更大的节点,这个节点就是两个节点的最近公共祖先。

36.png

37.png

38.png

39.png

代码实现

/**
 * 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 == null) {
            return null;
        }
        if(root == p || root == q) {
            return root;
        }
        TreeNode leftRet = lowestCommonAncestor(root.left,p,q);
        TreeNode rightRet = lowestCommonAncestor(root.right,p,q);
        if(leftRet != null && rightRet != null) {
            return root;
        }else if(leftRet != null) {
            return leftRet;
        }else {
            return rightRet;
        }
    }
}

40.png

方法二

第二种方法我们可以借用栈这种数据结构来解决,我们可以将从根节点到这两个节点路径上的节点分别放在两个栈中。然后得到了两个栈之后,我们比较栈中元素的大小,将栈中元素较大的站里面的元素弹出部分,使两个栈中的元素数量相等,接着我们就同时弹出两个栈中的元素并进行比较,如果相等就说明这个节点就是最近公共祖先。


但是我们怎样准确的将从根节点到该节点路径上的节点存放在栈中呢?


就像这个例子,我们需要找到节点5和节点4的公共祖先。

41.png

当我们找节点5路径上的节点时很容易找到,但是4呢?我们知道从根节点到节点4的路径的节点有3,5,2,4,但是我们怎样做才能不把6和7也算上呢?我们这样,当我们遍历完了5这个节点的左子树时,如果该节点的左子树或者右子树没有找到我们要找的两个节点,我们就将该左子树或者右子树上的节点从栈中弹出,最后栈中就只有从根节点到需要找的节点路径上的节点了。

43.png

44.png

45.png

46.png

47.png

48.png

49.png

50.png

代码实现

/**
 * 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) {
        Deque<TreeNode> stack1 = new ArrayDeque<>();
        Deque<TreeNode> stack2 = new ArrayDeque<>();
        lowestCommonAncestorChild(root,p,stack1);
        lowestCommonAncestorChild(root,q,stack2);
        int len = stack1.size() - stack2.size();
        if(len < 0) {
            len = -len;
            while(len > 0) {
                stack2.pop();
                len--;
            }
        }else {
            while(len > 0) {
                stack1.pop();
                len--;
            }
        }
        while(!stack1.isEmpty()) {
            if(stack1.peek() == stack2.peek()) {
                return stack1.peek();
            }
            stack1.pop();
            stack2.pop();
        }
        return null;
    }
    private boolean lowestCommonAncestorChild(TreeNode root,TreeNode node,Deque stack) {
        if(root == null) {
            return false;
        }
        stack.push(root);
        if(root == node) {
            return true;
        }
        boolean ret1 = lowestCommonAncestorChild(root.left,node,stack);
        //当我们在该节点的左树中找到了需要找的节点,说明该节点不需要弹出,
        //我们直接返回,节省时间
        if(ret1 == true) {
            return true;
        }
        boolean ret2 = lowestCommonAncestorChild(root.right,node,stack);
        if(ret2 == true) {
            return true;
        }
        //当该节点的左树和右树都没有时,我们就需要弹出该节点
        stack.pop();
        return false;
    }
}

image.png


根据二叉树创建字符串

根据二叉树创建字符串(难度:简单)


题目要求

给你二叉树的根节点 root ,请你采用前序遍历的方式,将二叉树转化为一个由括号和整数组成的字符串,返回构造出的字符串。


空节点使用一对空括号对 “()” 表示,转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。


示例 1:

image.png

输入:root = [1,2,3,4]

输出:“1(2(4))(3)”

解释:初步转化后得到 “1(2(4)())(3()())” ,但省略所有不必要的空括号对后,字符串应该是"1(2(4))(3)" 。


示例 2:

53.png

输入:root = [1,2,3,null,4]

输出:“1(2()(4))(3)”

解释:和第一个示例类似,但是无法省略第一个空括号对,否则会破坏输入与输出一一映射的关系。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public String tree2str(TreeNode root) {
    }
}

做题思路

根据实例我们可以知道,当根节点的左树和右树不为null时,我们需要在添加节点之前加入一个

“(”,当左树或者右树遍历完之后我们加上")“。当左树不为null时,我们正常进行遍历;当左树为null,右树不为null时,我们需要添加”()",然后再遍历右子树,当右树不为null时,我们正常加

“(“和”)”,当右树为null时,什么都不需要做。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public String tree2str(TreeNode root) {
        StringBuilder str = new StringBuilder();
        tree2strChild(root,str);
        return str.toString();
    }
    public void tree2strChild(TreeNode root,StringBuilder str) {
        if(root == null) {
            return;
        }
        str.append(root.val);
        if(root.left != null) {
            str.append("(");
            tree2strChild(root.left,str);
            str.append(")");
        }else {
            if(root.right != null) {
                str.append("()");
            }else {
                return;
            }
        }
        if(root.right != null) {
            str.append("(");
            tree2strChild(root.right,str);
            str.append(")");
        }else {
            return;
        }
    }
}

54.png


相关文章
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
1月前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
43 1
|
3月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
|
2月前
【LeetCode 31】104.二叉树的最大深度
【LeetCode 31】104.二叉树的最大深度
26 2
|
2月前
【LeetCode 29】226.反转二叉树
【LeetCode 29】226.反转二叉树
20 2
|
2月前
【LeetCode 28】102.二叉树的层序遍历
【LeetCode 28】102.二叉树的层序遍历
18 2
|
2月前
【LeetCode 43】236.二叉树的最近公共祖先
【LeetCode 43】236.二叉树的最近公共祖先
21 0
|
2月前
【LeetCode 38】617.合并二叉树
【LeetCode 38】617.合并二叉树
15 0
|
2月前
【LeetCode 37】106.从中序与后序遍历构造二叉树
【LeetCode 37】106.从中序与后序遍历构造二叉树
23 0
|
2月前
【LeetCode 34】257.二叉树的所有路径
【LeetCode 34】257.二叉树的所有路径
22 0