Leetcode刷题41-50

2023-12-19

Word count: 2.8k | Reading time≈ 12 min

①653.两数之和 Ⅳ - 输入二叉搜索树

题目：给定一个二叉搜索树 root 和一个目标结果 k ，如果二叉搜索树中存在两个元素且它们的和等于给定的目标结果，则返回 true。

表中若存在 k - root.val 则存在

深度优先搜索 + 哈希表

class Solution {
    Set<Integer> set = new HashSet<Integer>();
    public boolean findTarget(TreeNode root, int k) {
        if(root == null){
            return false;
        }
        if(set.contains(k - root.val)){
            return true;
        }
        set.add(root.val);
        return findTarget(root.left,k) || findTarget(root.right,k);
    }
}

广度优先搜索 + 哈希表

class Solution {
    public boolean findTarget(TreeNode root, int k) {
        Set<Integer> set = new HashSet<Integer>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(set.contains(k - node.val)){
                return true;
            }
            set.add(node.val);
            if(node.left != null){
                queue.add(node.left);
            }
            if(node.right != null){
                queue.add(node.right);
            }
        }
        return false;
    }
}

②617.合并二叉树

题目：给你两棵二叉树： root1 和 root2 。
想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。
合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；
否则，不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。

深度优先搜索

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1 == null){
            return root2;
        }
        if(root2 == null){
            return root1;
        }
        TreeNode merge = new TreeNode(root1.val + root2.val);
        merge.left = mergeTrees(root1.left,root2.left);
        merge.right = mergeTrees(root1.right,root2.right);
        return merge;
    }
}

③700.二叉搜索树中的搜索

题目：给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
你需要在 BST 中找到节点值等于 val 的节点。返回以该节点为根的子树。如果节点不存在，则返回 null 。

迭代和递归都是解决问题的常见方法，它们的主要区别在于解决问题的方式和实现细节。

原理不同
迭代是通过循环重复执行一定的语句来解决问题。每次迭代都是在处理相同的问题，但是问题的规模可能不同。
递归是通过函数自身循环调用来解决问题。每次递归都是在处理一个更小规模的子问题，直到达到基本情况或者边界条件。
实现方法不同
迭代可以使用循环结构来实现，它通常需要维护一些局部变量来保存每次迭代的结果，以便下一次迭代使用。
递归可以使用函数自身来实现，它需要考虑基础情况和递归调用的退出条件，通常需要使用堆栈来保存中间计算的结果。
效率不同
迭代通常比递归效率高，因为在迭代过程中，不需要频繁地进行函数调用和堆栈操作，同时还可以利用循环展开等优化方法提高效率。
而在递归过程中，由于需要频繁进行函数调用和堆栈操作，消耗的时间和内存资源通常会更多。
可读性不同
迭代通常比递归更易读和理解，因为迭代的实现方式更接近人们的思维方式，容易理解迭代每一步的处理过程。
而在递归中，由于需要不断调用函数自身来处理子问题，容易出现复杂的嵌套和逻辑流程，导致代码可读性降低。
综上所述，迭代和递归各有优缺点，需要根据具体情况选择合适的方法来解决问题。

递归

public TreeNode searchBST(TreeNode root, int val) {
       if(root == null){
           return null;
       }
       if(val == root.val){
           return root;
       }
       return searchBST(val < root.val?  root.left : root.right,val);
   }

迭代

public TreeNode searchBST(TreeNode root, int val) {
        while(root != null){
            if(root.val == val){
                return root;
            }
            root = val < root.val ? root.left : root.right;
        }
        return null;
    }

④783.二叉搜索树节点最小距离

题目：给你一个二叉搜索树的根节点 root ，返回树中任意两不同节点值之间的最小差值。
差值是一个正数，其数值等于两值之差的绝对值。

思考：
中序遍历得到升序
在遍历过程中调用最小值方法
cur - pre 当前-前一个
相邻两元素之差的最小值

class Solution {
    int pre;
    int result;
    public int minDiffInBST(TreeNode root) {
        pre = -1;
        result = Integer.MAX_VALUE;
        dfs(root);
        return result;
    }
    public void dfs(TreeNode root){
        if(root == null){
            return;
        }
        dfs(root.left);
        if(pre == -1){
            pre = root.val;
        }else{
            result = Math.min(result,root.val - pre);
            pre = root.val;
        }
        dfs(root.right);
    }
}

⑤606.根据二叉树创建字符串

题目：给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。
空节点使用一对空括号对 “()” 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

思考：
左右孩子都无，都不加
只有左孩子，只给左孩子结果加括号，不用给右孩子加括号

当前结点左右孩子都有，都加
只有右孩子，需要给左孩子加空括号，右孩子结果加括号

递归

public String tree2str(TreeNode root) {
       if(root == null){
           return "";
       }
       if(root.left == null && root.right == null){
           return Integer.toString(root.val);
       }
       //只有右孩子为空，不用加空()
       if(root.right == null){
           return new StringBuilder().append(root.val).append("(").append(tree2str(root.left)).append(")").toString();
       }
       return new StringBuilder().append(root.val).append("(").append(tree2str(root.left)).append(")").append("(").append(tree2str(root.right)).append(")").toString();
   }

⑥872.叶子相似的树

题目：请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个叶值序列。
如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是叶相似的。
如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。

思考：
分别得到两颗树的叶值序列
比较是否相同

class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> res1 = new ArrayList<Integer>();
        if(root1 != null){
            getLeaf(root1,res1);
        }
        List<Integer> res2 = new ArrayList<Integer>();
        if(root2 != null){
            getLeaf(root2,res2);
        }
        return res1.equals(res2);

    }

    public void getLeaf(TreeNode root,List<Integer> res){
        if(root.left == null && root.right == null){
            res.add(root.val);
        }else{
            if(root.left != null){
                getLeaf(root.left,res);
            }
            if(root.right != null){
                getLeaf(root.right,res);
            }
        }
    }
}

⑦897.递增顺序搜索树

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

思考：中序遍历树，将其值放在一个列表中，遍历列表中值，生成新的树

中序遍历后生成新的树

class Solution {
    public TreeNode increasingBST(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        inorder(root,res);
        TreeNode increaseNode = new TreeNode(res.get(0));
        TreeNode curNode = increaseNode;
        for(int i = 1; i < res.size(); i++){
            curNode.right = new TreeNode(res.get(i));
            curNode = curNode.right;
        }
        return increaseNode;
    }

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

也可以用增强for循环

TreeNode increaseNode = new TreeNode(-1);
TreeNode curNode = increaseNode;
for(int i : res){
    curNode.right = new TreeNode(i);
    curNode = curNode.right;
}
return increaseNode.right;

思考：
不生成新的树，只改变树的左右孩子的指向关系
直接在原树上进行操作，使用原有结点，不建立一个全新的树
遍历到一个结点时，将其左孩子设置为null，上一个结点的右孩子设置为当前结点值

在中序遍历的过程中改变结点指向

class Solution {
    TreeNode curNode;
    public TreeNode increasingBST(TreeNode root) {
        TreeNode increaseNode = new TreeNode(-1);
        curNode = increaseNode;
        inorder(root);
        return increaseNode.right;
    }
    public void inorder(TreeNode root){
        if(root == null){
            return;
        }
        inorder(root.left);

        root.left = null;
        curNode.right = root;
        curNode = root;

        inorder(root.right);
    }
}

在原树上进行的操作：
root.left = null;
curNode.right = root;
curNode = root;

⑧938.二叉搜索树的范围和

题目：给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。

思考：
二叉搜索树根节点左孩子值均小于根节点，右孩子均大于根节点
可以根据根节点的值判断所需范围的结点[low, high]分布在哪个位置

深度优先搜索

public int rangeSumBST(TreeNode root, int low, int high) {
       if(root == null){
           return 0;
       }
       if(root.val > high){
           return rangeSumBST(root.left,low,high);
       }
       if(root.val < low){
           return rangeSumBST(root.right,low,high);
       }
       return root.val + rangeSumBST(root.left,low,high) + rangeSumBST(root.right,low,high);

   }

广度优先搜索

public int rangeSumBST(TreeNode root, int low, int high) {
        int sum = 0;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node == null){
                continue;
            }
            if(node.val > high){
                queue.offer(node.left);
            }else if(node.val < low){
                queue.offer(node.right);
            }else{
                sum += node.val;
                queue.offer(node.left);
                queue.offer(node.right);
            }
        }
        return sum;
    }

⑨965.单值二叉树

题目：如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时，才返回 true；否则返回 false。

思考：
子节点不为 null 时，若和当前节点值不相同or以该孩子结点为根的树不符合单值二叉树时就不满足

深度优先搜索

public boolean isUnivalTree(TreeNode root) {
        if(root == null){
            return true;
        }
        if(root.left != null){
            if(root.left.val != root.val || !isUnivalTree(root.left)){
                return false;
            }
        }
        if(root.right != null){
            if(root.right.val != root.val || !isUnivalTree(root.right)){
                return false;
            }
        }
        return true;
    }

更简便

class Solution {
    public boolean isUnivalTree(TreeNode root) {
        return getResult(root,root.val);
    }
    public boolean getResult(TreeNode root ,int val){
        if(root == null){
            return true;
        }
        return root.val == val && getResult(root.left,val) && getResult(root.right,val);
    }
}

⑩1022.从根到叶的二进制数之和

题目：给出一棵二叉树，其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。
返回这些数字之和。题目数据保证答案是一个 32 位整数。

位运算：val = (val << 1) | root.val;

class Solution {
    public int sumRootToLeaf(TreeNode root) {
        return getSum(root,0);

    }
    //val是当前路径和
    public int getSum(TreeNode root,int val){
        if(root == null){
            return 0;
        }
        val = (val << 1) | root.val;
        if(root.left == null && root.right == null){
            return val;
        }
        return getSum(root.left,val) + getSum(root.right,val);
    }
}

Donate

Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.