LeetCode算法练习top100：（5）二叉树

太过爱你忘了你带给我的痛 2024-02-18 13:04 27阅读 0赞

package top100.top二叉树;
    
    import top100.TreeNode;
    
    import java.util.*;
    
    public class TOP {
        
        //94. 二叉树的中序遍历
        List<Integer> res = new ArrayList<>();
        public List<Integer> inorderTraversal(TreeNode root) {
        
            inorder(root);
            return res;
        }
        private void inorder(TreeNode root) {
        
            if (root != null) {
        
                inorder(root.left);
                res.add(root.val);
                inorder(root.right);
            }
        }
    
    
        //104. 二叉树的最大深度
        int maxDepth = 0;
        public int maxDepth(TreeNode root) {
        
            if (root == null) {
        
                return maxDepth;
            }
            dfsMaxDepth(root, 0);
            return maxDepth;
        }
        private void dfsMaxDepth(TreeNode root, int res) {
        
            if (root == null) {
        
                maxDepth = Math.max(maxDepth, res);
            } else {
        
                dfsMaxDepth(root.left, res + 1);
                dfsMaxDepth(root.right, res + 1);
            }
        }
    
    
        //226. 翻转二叉树
        public TreeNode invertTree(TreeNode root) {
        
            if (root == null) {
        
                return null;
            }
            TreeNode right = root.right;
            root.right = root.left;
            root.left = right;
            invertTree(root.left);
            invertTree(root.right);
            return root;
        }
    
    
        //101. 对称二叉树
        public boolean isSymmetric(TreeNode root) {
        
            if (root == null) {
        
                return true;
            }
            return isSymmetric(root.left, root.right);
        }
        public boolean isSymmetric(TreeNode left, TreeNode right) {
        
            if (left == null && right == null) {
        
                return true;
            } else if (left == null || right == null) {
        
                return false;
            } else if (left.val != right.val) {
        
                return false;
            } else {
        
                return isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
            }
        }
    
    
        //543. 二叉树的直径
        int diameterOfBinaryTree = 0;
        public int diameterOfBinaryTree(TreeNode root) {
        
            dfsDiameterOfBinaryTree(root);
            return diameterOfBinaryTree;
        }
        //计算当前节点到其叶子节点的最长距离
        private int dfsDiameterOfBinaryTree(TreeNode root) {
        
            if (root == null) return 0;
            //左右节点的最长距离
            int l = dfsDiameterOfBinaryTree(root.left);
            int r = dfsDiameterOfBinaryTree(root.right);
            diameterOfBinaryTree = Math.max(diameterOfBinaryTree, l + r);
            return Math.max(l, r) + 1;
        }
    
    
        //102. 二叉树的层序遍历
        public List<List<Integer>> levelOrder(TreeNode root) {
        
            List<List<Integer>> res = new ArrayList<>();
            if (root == null) {
        
                return res;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()) {
        
                int n = queue.size();
                List<Integer> list = new ArrayList<>();
                for (int i = 0; i < n; i++) {
        
                    TreeNode node = queue.poll();
                    list.add(node.val);
                    if (node.left != null) {
        
                        queue.add(node.left);
                    }
                    if (node.right != null) {
        
                        queue.add(node.right);
                    }
                }
                res.add(list);
            }
            return res;
        }
    
    
        //108. 将有序数组转换为二叉搜索树
        public TreeNode sortedArrayToBST(int[] nums) {
        
            if (nums.length == 0) return null;
            int start = 0, mid = (nums.length - 1) / 2;
            TreeNode root = new TreeNode(nums[mid]); //二叉搜索树的根节点是中序遍历数组中间的数
            if (mid - start > 0) {
         //如果数组可以构成左子树
                root.left = sortedArrayToBST(Arrays.copyOfRange(nums, start, mid));
            }
            if (mid < nums.length - 1) {
         //如果数组可以构成右子树
                root.right = sortedArrayToBST(Arrays.copyOfRange(nums, mid + 1, nums.length));
            }
            return root;
        }
    
    
        //98. 验证二叉搜索树
        long preVal = Long.MIN_VALUE; //为了通过测试用例，设置比int最小还要小的值
        public boolean isValidBST(TreeNode root) {
        
            if (root == null) return true;
            //先判断左子树是否满足
            if (!isValidBST(root.left)) {
        
                return false;
            }
            //中序是否满足递增
            if (root.val <= preVal) {
        
                return false;
            }
            preVal = root.val; //更新pre值
            //判断又子树
            return isValidBST(root.right);
        }
    
    
        //230. 二叉搜索树中第K小的元素
        int res1;
        int k;
        ArrayList<Integer> list = new ArrayList<>();
        public int kthSmallest(TreeNode root, int k) {
        
            this.k = k;
            inOrder(root, k);
            return res1;
        }
        //中序遍历,从最小结点开始遍历:二叉搜索树的中序遍历为递增序列
        private void inOrder(TreeNode root, int k) {
        
            if (root == null) return;
            if (root.left != null) {
        
                inOrder(root.left, k);
            }
            list.add(root.val);
            if (list.size() == k) {
        
                res1 = root.val;
                return;
            }
            if (root.right != null) {
        
                inOrder(root.right, k);
            }
        }
        //230. 二叉搜索树中第K小的元素
        int res1;
        int k;
        public int kthSmallest(TreeNode root, int k) {
        
            this.k = k;
            inOrder(root);
            return res1;
        }
        private void inOrder(TreeNode root) {
        
            if (root == null) return;
            //先递归到左端点
            inOrder(root.left);
            if (k == 0) return;
            //遍历到第k个
            if (--k == 0) res1 = root.val;
            //中序遍历
            inOrder(root.right);
        }
    
    
        //199. 二叉树的右视图
        public List<Integer> rightSideView(TreeNode root) {
        
            List<Integer> res = new ArrayList<>();
            if (root == null) {
        
                return res;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()) {
        
                int n = queue.size();
                for (int i = 0; i < n; i++) {
        
                    TreeNode cur = queue.poll();
                    if (i == n - 1) {
        
                        res.add(cur.val);
                    }
                    if (cur.left != null) {
        
                        queue.add(cur.left);
                    }
                    if (cur.right != null) {
        
                        queue.add(cur.right);
                    }
                }
            }
            return res;
        }
    
    
        //114. 二叉树展开为链表
        //方法1：逆前序遍历
        TreeNode preTreeNode = null;
        public void flatten(TreeNode root) {
        
            if (root == null) {
        
                return;
            }
            flatten(root.right);
            flatten(root.left);
            root.left = null;
            root.right = preTreeNode;
            preTreeNode = root;
        }
        //方法2：前序遍历后重组
        public void flatten(TreeNode root) {
        
            ArrayList<TreeNode> list = new ArrayList<>();
            preOder(root, list);
            for (int i = 1; i < list.size(); i++) {
        
                TreeNode pre = list.get(i - 1);
                TreeNode cur = list.get(i);
                pre.left = null;
                pre.right = cur;
            }
        }
        private void preOder(TreeNode root, ArrayList<TreeNode> list) {
        
            if (root != null) {
        
                list.add(root);
                if (root.left != null) {
        
                    preOder(root.left, list);
                }
                if (root.right != null) {
        
                    preOder(root.right, list);
                }
            }
        }
    
    
        //105. 从前序与中序遍历序列构造二叉树
        public TreeNode buildTree(int[] preorder, int[] inorder) {
        
            int n = preorder.length;
            if (n == 0) return null;
            TreeNode root = new TreeNode(preorder[0]);
            //获取根节点在中序的位置
            int mid = 0;
            for (int i = 0; i < n; i++) {
        
                if (inorder[i] == preorder[0]) {
        
                    mid = i;
                    break;
                }
            }
            //构造左右子树
            root.left = buildTree(Arrays.copyOfRange(preorder, 1, mid + 1), Arrays.copyOfRange(inorder, 0, mid));
            root.right = buildTree(Arrays.copyOfRange(preorder, mid + 1, preorder.length), Arrays.copyOfRange(inorder, mid + 1, inorder.length));
            return root;
        }
    
    
        //437. 路径总和 III
        int res4 = 0;
        //从每个节点dfs
        public int pathSum(TreeNode root, int targetSum) {
        
            if (root == null) return 0;
            //遍历每个节点 bfs
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()) {
        
                int n = queue.size();
                for (int i = 0; i < n; i++) {
        
                    TreeNode cur = queue.poll();
                    dfs4(cur, targetSum);
                    if (cur.left != null) queue.add(cur.left);
                    if (cur.right != null) queue.add(cur.right);
                }
            }
            return res4;
        }
        private void dfs4(TreeNode root, long curSum) {
        
            if (root != null) {
        
                curSum -= root.val;
                if (curSum == 0) {
        
                    res4++;
                }
                //递归
                dfs4(root.left, curSum);
                dfs4(root.right, curSum);
            }
        }
    
    
        //236. 二叉树的最近公共祖先
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
            if(root == null || root == p || root == q) return root;
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            if(left == null) return right;
            if(right == null) return left;
            return root;
        }
    
    
        //124. 二叉树中的最大路径和
        int res = Integer.MIN_VALUE;
        public int maxPathSum(TreeNode root) {
        
            dfs6(root);
            return res;
        }
        //计算root作为父结点所在在路径的最大路径和
        private int dfs6(TreeNode root) {
        
            if (root == null) return 0;
            //计算左子树的最大路径和,抛弃负数的路径
            int left = Math.max(0, dfs6(root.left));
            int right = Math.max(0, dfs6(root.right));
            //计算路径 left -> root -> right 的和
            res = Math.max(res, left + right + root.val);
            //返回root结点所在的子树最大路径和给父结点使用
            return root.val + Math.max(left, right);
        }
    }