力扣刷题之二叉树专栏

系统管理员 2023-09-25 12:47 52阅读 0赞

#### 文章目录 ####

*  一、2022/11/07
 *  二、2022/11/08
 *  三、2022/11/09
 *  四、2022/11/10

--------------------

加油，不要过度焦虑(꒪ꇴ꒪(꒪ꇴ꒪

--------------------

## 一、2022/11/07 ##

*  递归实现二叉树的前序、中序、后序遍历：

/**
     * @Auther: sht2002
     * @Date: 2022-11-07 17:40
     * @Description:前序遍历
     */
    public class Code01 {
        
        public List<Integer> preorderTraversal(TreeNode root) {
        
            List<Integer> list = new ArrayList<>();
            preorder(root, list);
            return list;
        }
        private void preorder(TreeNode root, List<Integer> list) {
        
            if (root == null) return;
            list.add(root.val);
            preorder(root.left, list);
            preorder(root.right, list);
        }
    }

/**
     * @Auther: sht2002
     * @Date: 2022-11-07 17:54
     * @Description:中序遍历
     */
    public class Code02 {
        
        public List<Integer> inorderTraversal(TreeNode root) {
        
            List<Integer> list = new ArrayList<>();
            inorder(root, list);
            return list;
        }
        private void inorder(TreeNode root, List<Integer> list) {
        
            if (root == null) return;
            inorder(root.left, list);
            list.add(root.val);
            inorder(root.right, list);
        }
    }

/**
     * @Auther: sht2002
     * @Date: 2022-11-07 17:54
     * @Description:后序遍历
     */
    public class Code03 {
        
        public List<Integer> postorderTraversal(TreeNode root) {
        
            List<Integer> list = new ArrayList<>();
            postorder(root, list);
            return list;
        }
        private void postorder(TreeNode root, List<Integer> list) {
        
            if (root == null) return;
            postorder(root.left, list);
            postorder(root.right, list);
            list.add(root.val);
        }
    }

*  迭代实现二叉树的前序、中序、后序遍历：

/**
     * @Auther: sht2002
     * @Date: 2022-11-07 18:16
     * @Description:前序遍历
     */
    public class Code04 {
        
        public List<Integer> preorderTraversal(TreeNode root) {
        
            List<Integer> list = new ArrayList<>();
            if (root == null) return list;
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
            while (!stack.isEmpty()) {
        
                TreeNode node = stack.pop();
                list.add(node.val);
                if (node.right != null) {
        
                    stack.push(node.right);
                }
                if (node.left != null) {
        
                    stack.push(node.left);
                }
            }
            return list;
        }
    }

/**
     * @Auther: sht2002
     * @Date: 2022-11-07 18:45
     * @Description:中序遍历
     */
    public class Code06 {
        
        public List<Integer> inorderTraversal(TreeNode root) {
        
            List<Integer> list = new ArrayList<>();
            if (list == null) return list;
            Stack<TreeNode> stack = new Stack<>();
            TreeNode temp = root;
            while (temp != null || !stack.isEmpty()) {
        
                if (temp != null) {
        
                    stack.push(temp);
                    temp = temp.left;
                } else {
        
                    temp = stack.pop();
                    list.add(temp.val);
                    temp = temp.right;
                }
            }
            return list;
        }
    }

/**
     * @Auther: sht2002
     * @Date: 2022-11-07 18:25
     * @Description:后序遍历
     */
    public class Code05 {
        
        public List<Integer> postorderTraversal(TreeNode root) {
        
            List<Integer> list = new ArrayList<>();
            if (root == null) return list;
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
            while (!stack.isEmpty()) {
        
                TreeNode node = stack.pop();
                list.add(node.val);
                if (node.left != null) {
        
                    stack.push(node.left);
                }
                if (node.right != null) {
        
                    stack.push(node.right);
                }
            }
            Collections.reverse(list);
            return list;
        }
    }

--------------------

## 二、2022/11/08 ##

*  参考文章：[图解BFS和DFS算法][BFS_DFS]
 *  Code01和Code02的代码一定要弄明白，后面几题都是用它们当做模板！！！

/**
     * @Auther: sht2002
     * @Date: 2022-11-08 17:25
     * @Description:二叉树的层序遍历：迭代方式 BFS
     */
    public class Code01 {
        
        public List<List<Integer>> levelOrder(TreeNode root) {
        
            List<List<Integer>> resList = new ArrayList<List<Integer>>();
            if (root == null) return resList;
            LinkedList<TreeNode> que = new LinkedList<TreeNode>();
            que.add(root);
            while (!que.isEmpty()) {
        
                List<Integer> list = new ArrayList<>();
                int len = que.size();
                while (len > 0) {
        
                    TreeNode node = que.poll();
                    list.add(node.val);
                    if (node.left != null) que.add(node.left);
                    if (node.right != null) que.add(node.right);
                    len--;
                }
                resList.add(list);
            }
            return resList;
    
        }
    }

/**
     * @Auther: sht2002
     * @Date: 2022-11-08 18:17
     * @Description:二叉树的层序遍历，递归方式 DFS
     */
    public class Code02 {
        
        List<List<Integer>> resList = new ArrayList<>();
        public List<List<Integer>> levelOrder(TreeNode root) {
        
            method(root, 0);
            return resList;
        }
        private void method(TreeNode node, Integer deep) {
        
            if (node == null) return;
            deep++;
            if (resList.size() < deep) {
        
                List<Integer> list = new ArrayList<>();
                resList.add(list);
            }
            resList.get(deep - 1).add(node.val);
            method(node.left, deep);
            method(node.right, deep);
        }
    }

/**
     * @Auther: sht2002
     * @Date: 2022-11-08 18:26
     * @Description:二叉树的层序遍历II,递归法
     */
    public class Code03 {
        
        List<List<Integer>> resList = new ArrayList<>();
        public List<List<Integer>> levelOrderBottom(TreeNode root) {
        
            method(root, 0);
            Collections.reverse(resList);
            return resList;
        }
        private void method(TreeNode node, Integer deep) {
        
            if (node == null) return;
            deep++;
            if (resList.size() < deep) {
        
                List<Integer> list = new ArrayList<>();
                resList.add(list);
            }
            resList.get(deep - 1).add(node.val);
            method(node.left, deep);
            method(node.right, deep);
        }
    }

/**
     * @Auther: sht2002
     * @Date: 2022-11-08 18:34
     * @Description:二叉树的层序遍历II,队列法BFS
     */
    public class Code04 {
        
        public List<List<Integer>> levelOrderBottom(TreeNode root) {
        
            List<List<Integer>> resList = new ArrayList<>();
            if (root == null) return resList;
            LinkedList<TreeNode> que = new LinkedList<>();
            que.add(root);
            while (!que.isEmpty()) {
        
                List<Integer> list = new ArrayList<>();
                int len = que.size();
                while (len > 0) {
        
                    TreeNode node = que.poll();
                    list.add(node.val);
                    len--;
                    if (node.left != null) que.add(node.left);
                    if (node.right != null) que.add(node.right);
                }
                resList.add(list);
            }
            Collections.reverse(resList);
            return resList;
        }
    }

/**
     * @Auther: sht2002
     * @Date: 2022-11-08 19:05
     * @Description:二叉树的右视图
     */
    public class Code05 {
        
        public List<Integer> rightSideView(TreeNode root) {
        
            List<Integer> resList = new ArrayList<>();
            if (root == null) return resList;
            LinkedList<TreeNode> que = new LinkedList<>();
            que.add(root);
            while (!que.isEmpty()) {
        
                int size = que.size();
                for (int i = 0; i < size; i++) {
        
                    TreeNode node = que.poll();
                    if (i == (size - 1)) resList.add(node.val);
                    if (node.left != null) que.add(node.left);
                    if (node.right != null) que.add(node.right);
                }
            }
            return resList;
        }
    }

## 三、2022/11/09 ##

*  此次刷题需要注意的是N叉树、完美二叉树的数据结构如何定义？

/**
     * @Auther: sht2002
     * @Date: 2022-11-09 18:12
     * @Description:二叉树的层平均值
     */
    public class Code01 {
        
        public List<Double> averageOfLevels(TreeNode root) {
        
            List<Double> resList = new ArrayList<>();
            if (root == null) return resList;
            LinkedList<TreeNode> que = new LinkedList<>();
            que.add(root);
            while (!que.isEmpty()) {
        
                int size = que.size();
                double sum = 0.0;
                for (int i = 0; i < size; i++) {
        
                    TreeNode node = que.poll();
                    sum += node.val;
                    if (node.left != null) que.add(node.left);
                    if (node.right != null) que.add(node.right);
                }
                resList.add(sum / size);
            }
            return resList;
        }
    }

*  [参考文章：什么是N叉树？][N]

/**
     * @Auther: sht2002
     * @Date: 2022-11-09 18:28
     * @Description: N叉树的层序遍历
     */
    public class Code02 {
        
        public List<List<Integer>> levelOrder(Node root) {
        
            List<List<Integer>> resList = new ArrayList<>();
            if (root == null) return resList;
            LinkedList<Node> que = new LinkedList<>();
            que.add(root);
            while (!que.isEmpty()) {
        
                int size = que.size();
                List<Integer> list = new ArrayList<>();
                for (int i = 0; i < size; i++) {
        
                    Node node = que.poll();
                    list.add(node.val);
                    if (node.children != null) {
        
                        int len = node.children.size();
                        for (int j = 0; j < len; j++) {
        
                            que.add(node.children.get(j));
                        }
                    }
                }
                resList.add(list);
            }
            return resList;
        }
    }

/**
     * @Auther: sht2002
     * @Date: 2022-11-09 18:48
     * @Description: 在每个树行中找最大值
     */
    public class Code03 {
        
        public List<Integer> largestValues(TreeNode root) {
        
            List<Integer> resList = new ArrayList<>();
            if (root == null) return resList;
            LinkedList<TreeNode> que = new LinkedList<>();
            que.add(root);
            while (!que.isEmpty()) {
        
                int size = que.size();
                int max = Integer.MIN_VALUE;
                for (int i = 0; i < size; i++) {
        
                    TreeNode node = que.poll();
                    max = Math.max(max, node.val);
                    if (node.left != null) que.add(node.left);
                    if (node.right != null) que.add(node.right);
                }
                resList.add(max);
            }
            return resList;
        }
    }

*  [参考文章：各种树的区别？][Link 1]

/**
     * @Auther: sht2002
     * @Date: 2022-11-09 18:57
     * @Description: 填充每个节点的下一个右侧节点指针
     */
    public class Code04 {
        
        public Node connect(Node root) {
        
            if (root == null) return null;
            LinkedList<Node> que = new LinkedList<>();
            que.add(root);
            while (!que.isEmpty()) {
        
                int size = que.size();
                for (int i = 0; i < size; i++) {
        
                    Node node = que.poll();
                    //if语句为true则说明该节点为此层的最后一个节点
                    if ((i + 1) == size) {
        
                        node.next = null;
                    } else {
        
                        Node anotherNode = que.peek();
                        node.next = anotherNode;
                    }
                    if (node.left != null) que.add(node.left);
                    if (node.right != null) que.add(node.right);
                }
            }
            return root;
        }
    }

/**
     * @Auther: sht2002
     * @Date: 2022-11-09 19:12
     * @Description: 填充每个节点的下一个右侧节点指针 II
     */
    public class Code05 {
        
        public Node connect(Node root) {
        
            if (root == null) return null;
            LinkedList<Node> que = new LinkedList<>();
            que.add(root);
            while (!que.isEmpty()) {
        
                int size = que.size();
                for (int i = 0; i < size; i++) {
        
                    Node node = que.poll();
                    //if语句为true则说明该节点为此层的最后一个节点
                    if ((i + 1) == size) {
        
                        node.next = null;
                    } else {
        
                        Node anotherNode = que.peek();
                        node.next = anotherNode;
                    }
                    if (node.left != null) que.add(node.left);
                    if (node.right != null) que.add(node.right);
                }
            }
            return root;
        }
    }

/**
     * @Auther: sht2002
     * @Date: 2022-11-09 19:21
     * @Description: 二叉树的最大深度
     */
    public class Code06 {
        
        public int maxDepth(TreeNode root) {
        
            if (root == null) return 0;
            LinkedList<TreeNode> que = new LinkedList<>();
            que.add(root);
            int sum = 0;
            while (!que.isEmpty()) {
        
                int size = que.size();
                sum++;
                for (int i = 0; i < size; i++) {
        
                    TreeNode node = que.poll();
                    if (node.left != null) que.add(node.left);
                    if (node.right != null) que.add(node.right);
                }
            }
            return sum;
        }
    }

/**
     * @Auther: sht2002
     * @Date: 2022-11-09 19:27
     * @Description: 二叉树的最小深度(思路：只有一个节点的左右节点都为null时，才是最小深度)
     */
    public class Code07 {
        
        public int minDepth(TreeNode root) {
        
            if (root == null) return 0;
            LinkedList<TreeNode> que = new LinkedList<>();
            que.add(root);
            int deep = 0;
            while (!que.isEmpty()) {
        
                int size = que.size();
                deep++;
                for (int i = 0; i < size; i++) {
        
                    TreeNode node = que.poll();
                    if (node.left == null && node.right == null) return deep;
                    if (node.left != null) que.add(node.left);
                    if (node.right != null) que.add(node.right);
                }
            }
            return deep;
        }
    }

--------------------

## 四、2022/11/10 ##

/**
     * @Auther: sht2002
     * @Date: 2022-11-10 19:05
     * @Description: 反转二叉树：再次加深对层序遍历的理解
     */
    public class Code01 {
        
        public TreeNode invertTree(TreeNode root) {
        
            if (root == null) return root;
            LinkedList<TreeNode> que = new LinkedList<>();
            que.add(root);
            while (!que.isEmpty()) {
        
                int size = que.size();
                for (int i = 0; i < size; i++) {
        
                    TreeNode node = que.poll();
                    swap(node);
                    if (node.left != null) que.add(node.left);
                    if (node.right != null) que.add(node.right);
                }
            }
            return root;
        }
        private void swap(TreeNode node) {
        
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;
        }
    }

/**
     * @Auther: sht2002
     * @Date: 2022-11-10 19:56
     * @Description: 对称二叉树
     */
    public class Code03 {
        
        public boolean isSymmetric(TreeNode root) {
        
            if (root == null) return true;
            return compare(root.left, root.right);
        }
        private boolean compare(TreeNode left, TreeNode right) {
        
            if (left == null && right != null) return false;
            else if (left != null && right == null) return false;
            else if (left == null && right == null) return true;
            else if (left.val != right.val) return false;
            //开始比较下面部分
            boolean res1 = compare(left.left, right.right);
            boolean res2 = compare(left.right, right.left);
            boolean res = res1 && res2;
            return res;
        }
    }

/**
     * @Auther: sht2002
     * @Date: 2022-11-10 19:38
     * @Description: 完全二叉树的节点个数
     */
    public class Code02 {
        
        public int countNodes(TreeNode root) {
        
            int count = 0;
            if (root == null) return count;
            LinkedList<TreeNode> que = new LinkedList<>();
            que.add(root);
            while (!que.isEmpty()) {
        
                int size = que.size();
                for (int i = 0; i < size; i++) {
        
                    TreeNode node = que.poll();
                    count++;
                    if (node.left != null) que.add(node.left);
                    if (node.right != null) que.add(node.right);
                }
            }
            return count;
        }
    }

[BFS_DFS]: https://blog.csdn.net/weixin_45705162/article/details/108296417
[N]: https://blog.csdn.net/qq_44671773/article/details/117520972
[Link 1]: https://www.cnblogs.com/idorax/p/6441043.html