• LeetCode刷题记录-简单模块（三）

    目录

    相同的树（深度优先搜索、广度优先搜索）
    给定两个二叉树的根节点，判断两棵树是否完全相同

    • 1

    对两棵树使用相同的方式遍历比较即可

    • 深度优先搜索
    /**
 * 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 boolean isSameTree(TreeNode p, TreeNode q) {
       //按照同样的顺序遍历两个树 然后对比
        if(p == null && q == null){
            return true;
        }
        if((p == null || q == null) || p.val != q.val){
            return false;
        }
        return tdoTrav(p.left , q.left) && doTrav(p.right , q.right);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 广度优先搜索
      二叉树的遍历方法一般是按照深度有限的原则，但是可以使用队列来实现广度优先的搜索，即按照树的层数一层一层的向下搜索
    class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
    	//使用队列作为暂存
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        while( !(queue.size()== 0  && p == null && q == null)){
            if(p == null && q == null){
                p = queue.poll();
                q = queue.poll();
                continue;
            }
            if(p == null || q == null || p.val != q.val){
                return false;
            }
            queue.add(p.left);
            queue.add(q.left);
            queue.add(p.right);
            queue.add(q.right);
            p = null;
            q = null;
        }
        return true;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    对称二叉树（深度优先搜索、广度优先搜索）
    给定一个二叉树，判断该二叉树是不是轴对称的

    • 1
    • 取出root节点的左子节点和右子节点，对两棵子树进行深度优先遍历
    class Solution {
    public boolean isSymmetric(TreeNode root) {
        //将树分为两棵树 完成后查看两棵树是否相同 使用深度优先检索
        if(root == null){
            return true;
        }
        return doTrav(root.left , root.right);

    }
    
    public boolean doTrav(TreeNode a , TreeNode b){
        if(a == null && b == null){
            return true;
        }
        if(a == null || b == null){
            return false;
        }
        if(a.val != b.val){
            return false;
        }
        //注意 这里不是比较两棵树是否是相同树，而是根据轴进行对称
        return doTrav(a.left , b.right) && doTrav(a.right , b.left);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 广度优先遍历root节点的两子树
    class Solution {
    public boolean isSymmetric(TreeNode root) {
        //使用迭代法处理 这里使用广度优先检索
        if(root == null){
            return true;
        }
        TreeNode p = root.left;
        TreeNode q = root.right;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        while(!(queue.isEmpty() && p == null && q == null)){
            if(p == null && q == null){
                p = queue.poll();
                q = queue.poll();
                continue;
            }
            if(p == null || q == null || p.val != q.val){
                return false;
            }
            queue.add(p.left);
            queue.add(q.right);
            queue.add(p.right);
            queue.add(q.left);
            p = null;
            q = null;
        }
        return true;
    }
    
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    二叉树的最大深度
    给定一个二叉树，请求出该二叉树的最大深度

    • 1
    • 深度优先遍历（递归调用）
    /**
 * 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 int maxDepth(TreeNode root) {
        //递归处理 整个二叉树的最大深度为根节点加上max(左子树最大深度，右子树最大深度)
        if(root == null){
            return 0;
        }
        return 1 + Math.max(maxDepth(root.left) ,maxDepth(root.right));
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 广度优先遍历
      同样可以使用队列来处理遍历，但是只有将当前层的节点全部处理完毕后才能继续向下层遍历。
    /**
 * 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 int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        //广度优先遍历
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        int depth = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            while(size > 0){
                root = queue.poll();
                if(root.left != null){
                    queue.add(root.left);
                }
                if(root.right != null){
                    queue.add(root.right);
                }
                size-- ;
            }
            depth ++;
        }
        return depth;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    将有序数组转换为平衡二叉树
    给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

    • 1
    • 2
    • 递归法处理
      因为给定的是有序数组，因此使用二分法找到每一段的中值作为节点即可
    /**
 * 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 TreeNode sortedArrayToBST(int[] nums) {
        TreeNode root = new TreeNode();
        doGetMid(root,nums , 0 , nums.length - 1);
        return root;
    }

    public void doGetMid(TreeNode root, int[] nums , int head , int tail){
        int tempMid =  head + (tail - head) / 2;
        root.val = nums[tempMid];
        if(tempMid - 1 >= head){
            root.left = new TreeNode();
            doGetMid(root.left , nums ,head , tempMid - 1 );
        }
        if(tempMid + 1 <= tail){
            root.right = new TreeNode();
            doGetMid(root.right , nums , tempMid + 1 , tail);
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    判断二叉树是不是平衡二叉树（递归）
    给定一个二叉树，当某个节点的左右子树之间的高度差大于1时，该二叉树不是平衡二叉树

    • 1
    • 由顶至尾递归遍历（时间复杂度O(n2)）
     *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    //确实纯想象的话是一个比较蠢的方法 因为有很多次递归 并且递归套递归
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        } else {
            return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        }
    }

    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            return Math.max(height(root.left), height(root.right)) + 1;
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 由尾至顶递归遍历（时间复杂度O(n)）
      方法一由于是自顶向下递归，因此对于同一个节点，函数会被重复调用，导致时间复杂度较高。如果使用自底向上的做法，则对于每个节点，函数只会被调用一次。
      自底向上递归的做法类似于后序遍历，对于当前遍历到的节点，先递归地判断其左右子树是否平衡，再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的，则返回其高度（高度一定是非负整数），否则返回 -1−1。如果存在一棵子树不平衡，则整个二叉树一定不平衡。
    class Solution {
    public boolean isBalanced(TreeNode root) {
        return height(root) >= 0;
    }

    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        } else {
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    二叉树的最小深度
    给定一个二叉树，请找出该二叉树的最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。

    • 1
    • 2

    只需要确定一点，当该节点没有左右子树时，可以认定为叶子节点。找出最近的叶子节点即可。

    • 广度优先遍历
    class Solution {
    public int minDepth(TreeNode root) {
        //尝试使用广度优先遍历处理
        if(root == null){
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        int minDepth = 1;
        queue.add(root);
        while(root != null || !queue.isEmpty()){
            int size = queue.size();
            while(size > 0){
                root = queue.poll();
                if(root.left == null && root.right == null){
                    return minDepth;
                }else{
                    if(root.left != null){
                        queue.add(root.left);
                    }
                    if(root.right != null){
                        queue.add(root.right);
                    }
                }
                size--;
            }
            minDepth++;
        }
        return minDepth;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 深度优先遍历
    class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        if (root.left == null && root.right == null) {
            return 1;
        }

        int min_depth = Integer.MAX_VALUE;
        if (root.left != null) {
            min_depth = Math.min(minDepth(root.left), min_depth);
        }
        if (root.right != null) {
            min_depth = Math.min(minDepth(root.right), min_depth);
        }

        return min_depth + 1;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    路径总和
    给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。
判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
如果存在，返回 true ；否则，返回 false 。

    • 1
    • 2
    • 3
    • DFS回溯算法
    class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null){
            return false;
        }
        targetSum -= root.val;
        if(root.left == null && root.right == null){
            if(targetSum != 0){
                return false;
            }else{
                return true;
            }
        }
        return hasPathSum(root.left , targetSum) || hasPathSum(root.right , targetSum) ;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
  • 相关阅读:
    如何使用pywinauto打开Windows上指定的应用程序
    若依（RuoYi ）权限管理设计
    福利又来了，mongo还不会快来练起来！操作汇总
    SCI如何审稿和修稿
    CMake教程（一）
    小结笔记：多位管理大师关于管理的要素的论述
    【毕业设计】信用卡欺诈检测系统 - python 大数据
    kali/debain/linux包管理
    Banana Pi BPI-M7 迷你尺寸开源硬件开发板采用瑞芯微RK3588芯片设计
    RabbitMQ 学习（四）-- 发布确认模式
  • 原文地址：https://blog.csdn.net/WOD_MAAYA/article/details/127671448