leetcode-hot-100-20230930

108. 将有序数组转换为二叉搜索树（Java递归实现）

/**
 * 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 digui(int [] nums, int left, int right){
        if(left > right){
            return null;
        }

        int mid = left + (right - left) / 2;
        TreeNode node = new TreeNode(nums[mid]);

        //单层递归逻辑
        //接受左子树结点
        node.left = digui(nums, left, mid - 1);
        //接受右子树结点
        node.right = digui(nums, mid + 1, right);

        return node;
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        //思路：使用递归方法
        TreeNode resultNode = digui(nums, 0, nums.length - 1);
        return resultNode;
    }
}

108. 将有序数组转换为二叉搜索树（Java使用迭代实现）

/**
 * 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) {
        //思路：使用迭代法实现
        //使用一个队列保存当前的树结点，使用一个队列保存左区间下标，使用一个队列保存有区间下标
        Queue<TreeNode> nodeQue = new LinkedList<>();
        //保存左边区间下标
        Queue<Integer> leftQue = new LinkedList<>();
        //保存右区间下标
        Queue<Integer> rightQue = new LinkedList<>();

        //创建一个新的树结点，添加到结点队列中
        TreeNode root = new TreeNode(0);
        nodeQue.offer(root);

        //将0设置添加到左区间队列中
        leftQue.offer(0);

        //将nums.length - 1添加到右区间队列中
        rightQue.offer(nums.length - 1);

        //循环遍历结点队列
        while(!nodeQue.isEmpty()){
            //获得当前结点
            TreeNode currNode = nodeQue.poll();
            int left = leftQue.poll();
            int right = rightQue.poll();

            //获得当前结点的val值
            int mid = left + (right - left) / 2;

            //给当前结点的val赋值
            currNode.val = nums[mid];

            //给currNode的left赋值
            //判断left与mid - 1的关系
            if(left <= mid - 1){
                //更新左区间队列
                currNode.left = new TreeNode(0);
                //将currNode添加到结点队列中
                nodeQue.offer(currNode.left);
                //将left对应的下标添加到左区间队列中
                leftQue.offer(left);
                //将right对应的下标添加到右区间队列中
                rightQue.offer(mid - 1);
            }

            //判断right与mid+1的大小关系
            if(right >= mid + 1){
                currNode.right = new TreeNode(0);
                nodeQue.offer(currNode.right);
                leftQue.offer(mid + 1);
                rightQue.offer(right);
            }
        }

        return root;
    }
}

98. 验证二叉搜索树（Java递归迭代遍历树结点，然后使用for循环遍历保存结点的数组检查是否升序排列即可）

/**
 * 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 {
    //创建保存二叉树结点的list
    List<TreeNode> keep = new ArrayList<>();

    //递归遍历二叉树
    public void digui(TreeNode root){
        if(root == null){
            return;
        }

        //单层递归逻辑
        //按照中左右的顺序
        digui(root.left);
        keep.add(root);
        digui(root.right);
        
        return ;
    }
    
    //参数为List<TreeNode>
    public boolean checkIsSouTree(List<TreeNode> keep){
        
        for(int i = 1;i < keep.size();i++){
            if(keep.get(i).val <= keep.get(i - 1).val){
                return false;
            }
        }

        return true;

    }

    public boolean isValidBST(TreeNode root) {
        //思路：输出二叉树的中序遍历结果，然后看是不是递增的
        digui(root);

        return checkIsSouTree(keep);

    }
}

230. 二叉搜索树中第K小的元素（Java递归实现）

/**
 * 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 {
    //保存结果数组
    List<Integer> keep = new ArrayList<>();

    //递归遍历二叉树
    public void TraverseTree(TreeNode root){
        if(root == null){
            return ;
        }

        //单层递归逻辑
        TraverseTree(root.left);
        keep.add(root.val);
        TraverseTree(root.right);

        return ;
    }

    public int kthSmallest(TreeNode root, int k) {
        //思路：遍历树结点值，对值进行排序
        TraverseTree(root);

        return keep.get(k - 1);
    }
}

199. 二叉树的右视图（Java使用队列实现）

/**
 * 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 List<Integer> rightSideView(TreeNode root) {
        //思路：使用二叉树的层次遍历，然后得到每层的最后一个元素
        //使用队列保存二叉树的结点
        List<Integer> result = new ArrayList<>();

        if(root == null){
            return result;
        }
        //创建队列
        Queue<TreeNode> nodeQue = new LinkedList<>();
        nodeQue.offer(root);

        while(!nodeQue.isEmpty()){
            //得到当前队列的长度
            int length = nodeQue.size();
            //保存当前层最后一个树结点
            TreeNode currLastNode = new TreeNode(0);

            //正常遍历队列
            for(int i = 0;i < length;i++){
                TreeNode node = nodeQue.poll();
                
                //更新最后一个树结点
                currLastNode = node;

                if(node.left != null){
                    nodeQue.offer(node.left);
                }

                if(node.right != null){
                    nodeQue.offer(node.right);
                }
            }

            //将每层最后一个树结点添加到result数组中
            result.add(currLastNode.val);
        }

        return result;
    }
}

114. 二叉树展开为链表（Java使用递归遍历，然后使用两个指针进行操作）

/**
 * 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 {
    
    List<TreeNode> keep = new ArrayList<>();

    public void digui(TreeNode root){
        if(root == null){
            return ;
        }
        //左右中
        keep.add(root);
        digui(root.left);
        digui(root.right);

        return ;
    }

    public void flatten(TreeNode root) {
        //思路：按照前序的顺序保存结点，然后更改结点的左右子结点即可
        digui(root);

        for(int i = 1;i < keep.size();i++){
            TreeNode prev = keep.get(i - 1);//得到前一个结点
            TreeNode curr = keep.get(i);//得到当前结点

            prev.left = null;
            prev.right = curr;
        }
        
    }
}

105. 从前序与中序遍历序列构造二叉树（Java实现）

/**
 * 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 buildTree(int[] preorder, int[] inorder) {
        //思路：根据前序遍历序列在中序遍历序列中根结点的位置i
        //用于更新下一段的中序遍历序列和前序遍历序列
        int preLength = preorder.length;
        int inLength = inorder.length;

        if(preLength == 0 || inLength == 0){
            return null;
        }

        TreeNode root = new TreeNode(preorder[0]);

        int k = 0;
        for(int i = 0;i < inLength;i++){
            if(preorder[0] == inorder[i]){
                k = i;
                break;
            }
        }

        //得到左子树对应的前序遍历序列
        //从1开始表示跳过当前创建的树木结点
        int [] leftPreorder = Arrays.copyOfRange(preorder, 1, k + 1);
        //得到左子树对应的中序遍历序列
        int [] leftInorder = Arrays.copyOfRange(inorder, 0, k);
        root.left = buildTree(leftPreorder, leftInorder);


        //得到右子树对应的前序遍历序列
        int [] rightPreorder = Arrays.copyOfRange(preorder, k + 1, preLength);
        int [] rightInorder = Arrays.copyOfRange(inorder, k + 1, inLength);
        root.right = buildTree(rightPreorder, rightInorder);

        return root;
    }
}