当前位置：首页 > article >正文

二叉树习题其五【力扣】【算法学习day.12】

article 2024/10/24 22:23:06

前言

书接上篇文章二叉树习题其四，这篇文章我们将基础拓展

###我做这类文档一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？）我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

习题

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

题目链接:236. 二叉树的最近公共祖先 - 力扣（LeetCode）

题面:

基本分析:如果一个节点的左右子树含有目标值，那么这个节点就是祖先，如果只有左/右子树含有，那这个就不是祖先

代码:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    TreeNode res;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        recursion(root,p.val,q.val);
        return res;
    }
    public int recursion(TreeNode node,int a,int b){
        if(node==null)return 0;
        int c = node.val==a|node.val==b?1:0;
        int left = recursion(node.left,a,b);
        int right = recursion(node.right,a,b);
        if(c+left+right==2)res = node;
        return c+left+right==0?0:1;
    }
}

2.二叉搜索树中的插入操作

题目链接:701. 二叉搜索树中的插入操作 - 力扣（LeetCode）

题面:

基本分析:根据二叉搜索树的规则一直遍历到空值然后插入即可

代码:

/**
 * 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 {
    int res;
    TreeNode flag;
    public TreeNode insertIntoBST(TreeNode root, int val) {
        // System.out.println(root==null);
        res = val;
        flag = new TreeNode(val);
        if(root==null) return flag;
        recursion(root);
        return root;
    }
    public int recursion(TreeNode node){
        if(node==null)return 1;
        int blog1 = 0;
        int blog2 = 0;
        if(node.val<res)blog1 = recursion(node.right);
        if(node.val>res)blog2 = recursion(node.left);
        if(blog1==1)node.right = flag;
        else if(blog2==1)node.left = flag;
        return 0;
    }
}

3.删除二叉搜索树中的节点

题目链接:450. 删除二叉搜索树中的节点 - 力扣（LeetCode）

题面:

基本分析:如果遍历到要删除的节点，分情况的讨论，如果左右节点都是空，就返回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 {
    int target;
    public TreeNode deleteNode(TreeNode root, int key) {
        target = key;
      if(root==null)return null;
      return  recursion(root);
    }
    public TreeNode recursion(TreeNode node){
        if(node==null)return null;
        if(node.val==target){
            if(node.left==null)return node.right;
            if(node.right==null)return node.left;
            TreeNode c = node.left;
            while(c.right!=null)c = c.right;
            c.right = node.right;
            return node.left;
        }else{
            if(node.val>target)node.left = recursion(node.left);
            else node.right = recursion(node.right);
        }
        return node;
    }
    
}