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

随想录笔记-二叉树练习题

article 2024/11/13 11:07:21

合并二叉树

617. 合并二叉树 - 力扣（LeetCode）

dfs递归

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
    if(root1==null||root2==null){
        return root1==null?root2:root1;
    }
    return  dfs(root1,root2);
    }
    public TreeNode dfs(TreeNode root1, TreeNode root2){
         if(root1==null||root2==null){
        return root1==null?root2:root1;
        }

        root1.val+=root2.val;
        root1.left=dfs(root1.left,root2.left);
        root1.right=dfs(root1.right,root2.right);
        return root1;
    }
}

类似的思路-对称二叉树

101. 对称二叉树 - 力扣（LeetCode）

class Solution {
    public boolean isSymmetric(TreeNode root) {
 if(root==null) return true;

 return compare(root.left,root.right);
}

public boolean compare(TreeNode left,TreeNode right){
    if(left==null&&right!=null) return false;
    if(left!=null&&right==null) return false;
    if(left==null&&right==null) return true;
    if(left.val!=right.val) return false;

    boolean inner=compare(left.right,right.left);
    boolean outside=compare(left.left,right.right);
    return inner&&outside;

}
}

bfs迭代

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
    if(root1==null||root2==null){
        return root1==null?root2:root1;
    }
    Queue<TreeNode> queue=new LinkedList<TreeNode>();
    queue.offer(root1);
    queue.offer(root2);
    while(!queue.isEmpty()){
        int len=queue.size();
        TreeNode t1=queue.poll();
        TreeNode t2=queue.poll();
        t1.val+=t2.val;
       
        if(t1.left!=null&&t2.left!=null){
            queue.offer(t1.left);
            queue.offer(t2.left);

        }else if(t1.left==null){
            t1.left=t2.left;
        }

        if(t1.right!=null&&t2.right!=null){
            queue.offer(t1.right);
            queue.offer(t2.right);

        }else if(t1.right==null){
            t1.right=t2.right;
        }

    }
    return root1;
    }
}

二叉搜索数中的搜索

利用二叉树的性质

首先我们需要知道二叉搜索树的一个关键性质：

二叉搜索树任意节点的左子树上所有节点值都小于这个节点；
二叉搜索树任意节点的右子树上所有节点值都大于这个节点；

700. 二叉搜索树中的搜索 - 力扣（LeetCode）

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
      if(root==null||root.val==val) return root;
      if(root.val>val) return searchBST(root.left,val);
      return searchBST(root.right,val);
    }
}

验证二叉搜索数

98. 验证二叉搜索树 - 力扣（LeetCode）

中序遍历

二叉搜索树的性质出发，中序遍历的情况下，后一个数比前一个数大

所以这里面的pre处理的非常好

98. 验证二叉搜索树 - 力扣（LeetCode）

 */
class Solution {
    long pre=Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
    if(root==null) return true;
    if(!isValidBST(root.left))
    return false;

    if(root.val<=pre)
    return false;

    pre=root.val;
    return isValidBST(root.right);
    }
}

前序遍历

这个代码我自己写的，但是我写的时候没有把边界作为参数传递进去，所以就无法判断子树与根节点的情况，只能判断以以子节点为根节点的数的情况

class Solution {
    public boolean isValidBST(TreeNode root) {
    if(root==null) return true;

    return deal(root,Long.MAX_VALUE,Long.MIN_VALUE);
   }
    public boolean deal(TreeNode root,long max,long min){
        if(root==null) return true;
       

       if(root.val<=min||root.val>=max) return false;

       return deal(root.left,root.val,min)&&deal(root.right,max,root.val);
      

    }
}

二叉搜索树的最小绝对差

min(root.left);
if(pre!=Integer.MIN_VALUE){
min=Math.min(min,Math.abs(root.val-pre));
}
pre=root.val;

min(root.right);

pre=root.val;回到根节点

要知道二叉搜索树和中序遍历是好朋友！

class Solution {
    int min=Integer.MAX_VALUE;
    int pre=Integer.MIN_VALUE;
    public int getMinimumDifference(TreeNode root) {
        
        min(root);
        return min;
     }
     public void min(TreeNode root){
        if(root==null) return ;
      
        min(root.left);
        if(pre!=Integer.MIN_VALUE){
            min=Math.min(min,Math.abs(root.val-pre));
        }
        pre=root.val;
  
        min(root.right);
     }
}

二叉搜索树中的众数

501. 二叉搜索树中的众数 - 力扣（LeetCode）

根据二叉搜索树的特点，对其进行中序遍历，得到一个有序数组，然后寻找重复的元素

注意！！这个的众数是出现频率最高的数，不是重复的数就是众数

class Solution {
    HashMap<Integer,Integer> map=new HashMap<>();

    public int[] findMode(TreeNode root) {
    
    List<Integer> list=new ArrayList<>();
    inorder(root,list);

    int pre=list.get(0);
    int len=1;
    int maxlen=1;
    List<Integer> res=new ArrayList<>();
    res.add(list.get(0));
    for(int i=1;i<list.size();i++){
        if(list.get(i)==pre){
            len=len+1;
        }else{
            len=1;
        }

        if(len==maxlen){
            res.add(list.get(i));

        }else if(len>maxlen){
            maxlen=len;
            res.clear();
            res.add(list.get(i));
        }
        pre=list.get(i);
    }
    return res.stream().mapToInt(Integer::intValue).toArray();
    }

 public void inorder(TreeNode root,List<Integer> list){
    if(root==null)
    return ;

    inorder(root.left,list);
    list.add(root.val);
    inorder(root.right,list);
 }
   
}

这个代码就是前一个代码的优化，在中序操作的时候把重复元素找出来，所以执行时间更快

501. 二叉搜索树中的众数 - 力扣（LeetCode）

class Solution {
    int maxCount = 1;
    int count = 1;
    TreeNode preNode = null;    // 存储前一个结点
    List<Integer> list = new ArrayList();   // 结果集
    public int[] findMode(TreeNode root) {
        // 中序遍历中，相同的元素都是一起出现的
        inOrder(root);
        int res[] = new int[list.size()];
        for(int i=0;i<list.size();i++) {
            res[i] = list.get(i);
        }
        return res;
    }
    public void inOrder(TreeNode root) {
        if(root == null) return ;
        inOrder(root.left);

        // 中序遍历的处理逻辑
        if(preNode!=null) {  // 非第一个元素的处理逻辑
            // 判断当前元素与前一个元素的关系，如果相同count++,不相同重新开始计数
            if(root.val==preNode.val) count++;
            else count=1;
            // 判断当前计数器与最大数的关系，如果相等就加入list，大于就清空list并加入
            if(count>maxCount) {
                maxCount = count;
                list.clear();
                list.add(root.val);
            } else if(count==maxCount)