Leetcode刷题51-60

①1379.找出克隆二叉树中的相同节点

题目：给你两棵二叉树，原始树 original 和克隆树 cloned，以及一个位于原始树 original 中的目标节点 target。
其中，克隆树 cloned 是原始树 original 的一个 副本 。
请找出在树 cloned 中，与 target 相同 的节点，并返回对该节点的引用。
注意：你 不能 对两棵二叉树，以及 target 节点进行更改。只能 返回对克隆树 cloned 中已有的节点的引用

中序遍历+递归

public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
       if(original == null){
           return null;
       }
       if(original == target){
           return cloned;
       }
       TreeNode node1 = getTargetCopy(original.left,cloned.left,target);
       if(node1 != null){
           return node1;
       }
       TreeNode node2 = getTargetCopy(original.right,cloned.right,target);
       if(node2 != null){
           return node2;
       }
       return null;
   }

层次遍历+队列

public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        Queue<TreeNode> clomedQueue = new LinkedList<TreeNode>();
        queue.offer(original);
        clomedQueue.offer(cloned);
        TreeNode node1;
        TreeNode node2;
        while(!queue.isEmpty()){
            node1 = queue.poll();
            node2 = clomedQueue.poll();
            if(node1 == target){
                return node2;
            }
            if(node1.left != null){
                queue.offer(node1.left);
                clomedQueue.offer(node2.left);
            }
            if(node1.right != null){
                queue.offer(node1.right);
                clomedQueue.offer(node2.right);
            }
        }
        return null;  
    }

②2331.计算布尔二叉树的值

题目：给你一棵 完整二叉树 的根，这棵树有以下特征：
叶子节点 要么值为 0 要么值为 1 ，其中 0 表示 False ，1 表示 True 。
非叶子节点 要么值为 2 要么值为 3 ， 其中 2 表示逻辑或 OR ，3 表示逻辑与 AND 。

计算 一个节点的值方式如下：
如果节点是个叶子节点，那么节点的 值 为它本身，即 True 或者 False 。
否则，计算 两个孩子的节点值，然后将该节点的运算符对两个孩子值进行 运算 。
返回根节点 root 的布尔运算值。

完整二叉树 是每个节点有 0 个或者 2 个孩子的二叉树。
叶子节点 是没有孩子的节点。

public boolean evaluateTree(TreeNode root) {
      if(root.left == null){
          return root.val == 1;
      }
      if(root.val == 2){
          return evaluateTree(root.left) || evaluateTree(root.right);
      }else{
          return evaluateTree(root.left) && evaluateTree(root.right);
      }
  }

③LCP 44.开幕式焰火

2023.12.31
题目：「力扣挑战赛」开幕式开始了，空中绽放了一颗二叉树形的巨型焰火。
给定一棵二叉树 root 代表焰火，节点值表示巨型焰火这一位置的颜色种类。
请帮小扣计算巨型焰火有多少种不同的颜色。

思路：将树的结点值存在哈希表中(不存在重复数字)，返回哈希白的长度，即不同颜色的种类

class Solution {
    Set<Integer> set = new HashSet<Integer>();
    public int numColor(TreeNode root) {
        dfs(root);
        return set.size();
    }
    public void dfs(TreeNode root){
        if(root == null) return;

        set.add(root.val); // 先序遍历
        dfs(root.left);
        dfs(root.right);
    }
}

④LCR 052.递增顺序搜索树

2024.1.1
题目：给你一棵二叉搜索树，请 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。

思路1：中序遍历，将结点的值放在List里面，用List里面的值产生一个全新的树

中序遍历后生成一颗新的树

class Solution {
    public TreeNode increasingBST(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        inorder(root,res);
        TreeNode result = new TreeNode(-1);
        TreeNode current = result;
        for(int value:res){
            current.right = new TreeNode(value);
            current = current.right;
        }
        return result.right;

    }

    public void inorder(TreeNode root,List res){
        if(root == null){
            return;
        }
        inorder(root.left,res);
        res.add(root.val);
        inorder(root.right,res);
    }
}

思路2：在中序遍历的过程中，直接在原有树的基础上改变原来结点的指向

current.right = root;
root.left = null;
current = root;

直接改变结点指向

class Solution {
    TreeNode current;
    public TreeNode increasingBST(TreeNode root) {
        TreeNode result = new TreeNode(-1);
        current = result;
        inorder(root);
        return result.right;


    }
     public void inorder(TreeNode root){
        if(root == null){
            return;
        }
        inorder(root.left);

        current.right = root;
        root.left = null;
        current = root;
        
        inorder(root.right);
    }
}

⑤LCR 193.二叉搜索树的最近公共祖先

2024.1.2
题目：给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，
满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。

说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。

思路：利用二叉搜索树的特点，如果p和q的值都小于根节点，则去左子树找，如果都大于根节点值则去右子树找，
如果刚好不在一边，则root就是它们的最近公共祖先(在两侧/有一点是root)

方法1

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
       if(root == null){
           return null;
       }
       if(p.val < root.val && q.val < root.val){
           return lowestCommonAncestor(root.left,p,q);
       }
       if(p.val > root.val && q.val > root.val){
           return lowestCommonAncestor(root.right,p,q);
       }
       return root;    
   }

方法2

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
      if(root == null || root == p || root == q || (root.val - p.val)*(root.val - q.val) < 0) return root;
      if(root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right,p,q);
      return lowestCommonAncestor(root.left,p,q);
  }

⑥LCR 144.翻转二叉树

2024.1.3
题目：给定一棵二叉树的根节点 root，请左右翻转这棵二叉树，并返回其根节点。

思路：交换左右子树

public TreeNode mirrorTree(TreeNode root) {
       if(root == null || root.left == null && root.right == null) return root;
       TreeNode left = root.left;
       root.left = mirrorTree(root.right);
       root.right = mirrorTree(left);
       return root;
   }

⑦LCR 145.判断对称二叉树

2024.1.4
请设计一个函数判断一棵二叉树是否 轴对称 。

思考：
对应轴对称位置结点，如果同为空则true，不同空则false
对应轴对称位置结点的值要相同
注意要判断根节点if(root == null) return true;

class Solution {
    public boolean checkSymmetricTree(TreeNode root) {
        if(root == null) return true;
        return check(root.left,root.right);
    }
    //判断对应结点的值是否相同
    public boolean check(TreeNode p,TreeNode q){
        if(p == null && q == null) return true;
        if(p == null || q == null) return false;
        return p.val == q.val && check(p.left,q.right) && check(p.right,q.left);
    }
}

⑧LCR 150.彩灯装饰记录Ⅱ

2024.1.5
题目：一棵圣诞树记作根节点为 root 的二叉树，节点值为该位置装饰彩灯的颜色编号。
请按照从左到右的顺序返回每一层彩灯编号，每一层的结果记录于一行

思考1：
每一层记录在一个 tempList 中，最终返回每一层List的集合
层次遍历：用队列
要把当前层的结点全部取出来放在tempList中，将tempList加入最终的List

层次遍历(广度优先)

public List<List<Integer>> decorateRecord(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if(root == null) return result;

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while(!queue.isEmpty()){
            //要确定poll出几个加在temp中
            int size = queue.size();
            List<Integer> temp = new ArrayList<Integer>();
            for(int i = 0;i < size;i++){
                TreeNode node = queue.poll();
                temp.add(node.val);
                //queue中加入下一层的结点
                if(node.left != null){
                    queue.offer(node.left);
                }
                if(node.right != null){
                    queue.offer(node.right);
                }
            }
            result.add(temp);
        }
        return result;
    }

思考2：
根据对应的层次，将该结点加入到对应深度的列表中

更优解(递归)

class Solution {
    public List<List<Integer>> decorateRecord(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        getResult(root,0,result);
        return result;
    }
    public void getResult(TreeNode root,int hight,List<List<Integer>> res){
        if(root == null) return;
        //建立新的一层(空层)
        if(res.size() == hight){
            res.add(new ArrayList<Integer>());
        }
        //将当前结点放在对应层的位置
        res.get(hight).add(root.val);

        getResult(root.left,hight+1,res);
        getResult(root.right,hight+1,res);
    }
}

⑨LCR 174.寻找二叉搜索树中的目标结点

2024.1.6
题目：某公司组织架构以二叉搜索树形式记录，节点值为处于该职位的员工编号。请返回第 cnt 大的员工编号。

思路1：中序遍历，得到升序序列

升序

class Solution {
    public int findTargetNode(TreeNode root, int cnt) {
        List<Integer> res = new ArrayList<Integer>();
        inorder(root,res);
        return res.get(res.size() - cnt);
    }
    public void inorder(TreeNode root,List<Integer> res){
        if(root == null) return;
        inorder(root.left,res);
        res.add(root.val);
        inorder(root.right,res);
    }
}

思路2：也可让其进行降序排列，在排列的过程中直接返回

降序 更好

class Solution {
    int sum;
    int res;
    public int findTargetNode(TreeNode root, int cnt) {
        getNode(root,cnt);
        return res;
    }
    public void getNode(TreeNode root,int cnt){
        if(root == null){
            return;
        }
        getNode(root.right,cnt);
        sum++;
        if(sum == cnt){
            res = root.val;
        }
        getNode(root.left,cnt);
    }
}

⑩LCR 175.计算二叉树的深度

2024.1.7
题目：某公司架构以二叉树形式记录，请返回该公司的层级数。

class Solution {
    public int calculateDepth(TreeNode root) {
        return getDepth(root);
    }
    public int getDepth(TreeNode root){
        if(root == null){
            return 0;
        }
        return 1 + Math.max(getDepth(root.left),getDepth(root.right));
    }
}

Donate