BST Mock

  • 开发
  • 14

700,98

 530,501,236

235,701,450

669，108，538

700. Search in a Binary Search Tree

Easy

You are given the root of a binary search tree (BST) and an integer val.

Find the node in the BST that the node's value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root;
        }
        if (val < root.val) {
            return searchBST(root.left, val);
        } else {
            return searchBST(root.right, val);
        }
    }
}

 

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        while (root != null) {
            if (val < root.val) {
                root = root.left;
            } else if (val > root.val) {
                root = root.right;
            } else {
                return root;
            }
        }
        return null;
    }
}
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root;
        }
        TreeNode left = searchBST(root.left, val);
        if (left != null) {
            return left;
        }
        return searchBST(root.right, val);
    }
}

98. Validate Binary Search Tree

Medium

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

  • The left 

    subtree

     of a node contains only nodes with keys less than the node's key.
  • The right subtree of a node contains only nodes with keys greater than the node's key.
  • Both the left and right subtrees must also be binary search trees.
class Solution {
    long pre = Long.MIN_VALUE;

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

 

class Solution {
    long pre = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        boolean left = isValidBST(root.left);
        if (pre >= root.val) {
            return false;
        }
        pre = root.val;
        boolean right = isValidBST(root.right);
        return left && right;
    }
}
class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return false;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        Long pre = Long.MIN_VALUE;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                TreeNode pop = stack.pop();
                if (pre >= pop.val) {
                    return false;
                }
                pre = (long) pop.val;
                cur = pop.right;
            }
        }
        return true;
    }
}

530. Minimum Absolute Difference in BST

Easy

Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.

class Solution {
    public int getMinimumDifference(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        TreeNode pre = null;
        int ans = Integer.MAX_VALUE;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                TreeNode pop = stack.pop();
                if (pre != null) {
                    ans = Math.min(pop.val - pre.val, ans);
                }
                pre = pop;
                cur = pop.right;
            }
        }
        return ans;
    }
}
class Solution {
    int ans = Integer.MAX_VALUE;
    TreeNode pre = null;

    public int getMinimumDifference(TreeNode root) {
        if (root == null) {
            return 0;
        }
        getMinimumDifference(root.left);
        if (pre != null) {
            ans = Math.min(ans, root.val - pre.val);
        }
        pre = root;
        getMinimumDifference(root.right);
        return ans;
    }
}

501. Find Mode in Binary Search Tree

Easy

Given the root of a binary search tree (BST) with duplicates, return all the mode(s) (i.e., the most frequently occurred element) in it.

If the tree has more than one mode, return them in any order.

Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than or equal to the node's key.
  • The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
  • Both the left and right subtrees must also be binary search trees.
class Solution {
    public int[] findMode(TreeNode root) {
        int count = 0;
        int maxCount = 0;
        TreeNode pre = null;
        List<Integer> list = new LinkedList<>();
        if (root == null) {
            return null;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                if (pre != null) {
                    if (pre.val == cur.val) {
                        count = count + 1;
                    } else {
                        count = 1;
                    }
                } else {
                    count = 1;
                }
                if (count > maxCount) {
                    maxCount = count;
                    list.clear();
                    list.add(cur.val);
                } else if (count == maxCount) {
                    list.add(cur.val);
                }
                pre = cur;
                cur = cur.right;
            }
        }
        return list.stream().mapToInt(Integer::intValue).toArray();
    }
}

 

class Solution {
    public int[] findMode(TreeNode root) {
        int count = 0;
        int maxCount = 0;
        TreeNode pre = null;
        List<Integer> list = new LinkedList<>();
        if (root == null) {
            return null;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                if (pre == null || cur.val != pre.val) {
                    count = 1;
                } else {
                    count++;
                }
                if (count > maxCount) {
                    maxCount = count;
                    list.clear();
                    list.add(cur.val);
                } else if (count == maxCount) {
                    list.add(cur.val);
                }
                pre = cur;
                cur = cur.right;
            }
        }
        return list.stream().mapToInt(Integer::intValue).toArray();
    }
}

236. Lowest Common Ancestor of a Binary Tree

Medium

Topics

Companies

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

class Solution {
    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 && right == null) { // 若未找到节点 p 或 q
            return null;
        }else if(left == null && right != null) { // 若找到一个节点
            return right;
        }else if(left != null && right == null) { // 若找到一个节点
            return left;
        }else { // 若找到两个节点
            return root;
        }
    }
}

235. Lowest Common Ancestor of a Binary Search Tree

Medium

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while (root != null) {
            if(root.val<p.val&&root.val<q.val){
                root = root.right;
            }else if(root.val>p.val&&root.val>q.val){
                root = root.left;
            }else {
               break;
            }
        }
        return root;
    }
}
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
        if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
        return root;
    }
}

701. Insert into a Binary Search Tree

Medium

You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

Notice that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return new TreeNode(val);
        }
        if (val < root.val) {
            root.left = insertIntoBST(root.left, val);
        } else if (val > root.val) {
            root.right = insertIntoBST(root.right, val);
        }
        return root;
    }
}
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        TreeNode curNode = root;
        TreeNode pre = root;
        while (curNode != null) {
            pre = curNode;
            if (val < curNode.val) {
                curNode = curNode.left;
            } else if (val > curNode.val) {
                curNode = curNode.right;
            } else {
                return root;
            }
        }
        if (val < pre.val) {
            pre.left = new TreeNode(val);
        } else {
            pre.right = new TreeNode(val);
        }
        return root;
    }
}

450. Delete Node in a BST

Medium

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

  1. Search for a node to remove.
  2. If the node is found, delete the node.
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return root;
        if (root.val == key) {
            if (root.right == null) {
                return root.left;
            } else {
                TreeNode cur = root.right;
                while (cur.left != null) {
                    cur = cur.left;
                }
                cur.left = root.left;
                root = root.right;
                return root;
            }
        }
        if (key < root.val) root.left = deleteNode(root.left, key);
        if (key > root.val) root.right = deleteNode(root.right, key);
        return root;
    }
}
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;

        if (root.val > key) {
            root.left = deleteNode(root.left,key);
        } else if (root.val < key) {
            root.right = deleteNode(root.right,key);
        } else {
            if (root.left == null) return root.right;
            if (root.right == null) return root.left;
            TreeNode tmp = root.right;
            while (tmp.left != null) {
                tmp = tmp.left;
            }
            root.val = tmp.val;
            root.right = deleteNode(root.right,tmp.val);
        }
        return root;
    }
}
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        //1.找到待删除节点
        //2.只有一个孩子的情况，直接托付给父节点。编写托孤方法
        //3.左右孩子都没有用2里的处理逻辑就可以了
        //4.左右孩子都有
        //左右孩子都有，则找到待删除节点的后继节点，记为S，其父节点记为SP
        //若S与待删除节点相邻，即后继节点是他的孩子，则直接将后继孩子节点S继承自己位置，将S托付给Parent
        //若后继节点不是他的孩子，则先把这个孩子节点的孩子托付给这个孩子的父亲SP，再让这个孩子顶替自己位置
        if (root == null) {
            return null;
        }
        TreeNode curNode = root;
        TreeNode parentNode = null;
        //找到需要删除的节点
        while (curNode != null) {
            if (key < curNode.val) {
                parentNode = curNode;
                curNode = curNode.left;
            } else if (key > curNode.val) {
                parentNode = curNode;
                curNode = curNode.right;
            } else {
                break;
            }
        }
        //没有找到
        if (curNode == null) {
            return root;
        }
        //如果只有一个孩子，直接把孩子托付给父节点（所以要记录父节点）
        if (curNode.left == null || curNode.right == null) {
            TreeNode newChild = (curNode.left == null) ? curNode.right : curNode.left;
            if (parentNode == null) {
                root = newChild;  // 这里处理如果删除的是根节点的情况
            } else {
                shift(parentNode, curNode, newChild);
            }
        } else {
            //左右孩子都有
            //4.1找到删除节点的后继(findPrePost里有)，这里一定有右子树，所以找后继的代码用不完
            TreeNode s = curNode.right;
            TreeNode sParent = curNode;
            while (s.left != null) {
                sParent = s;
                s = s.left;
            }
            //4.2后继节点不是待删除节点的孩子，则需要先处理掉后继节点的孩子，再让他继承
            if (curNode.right != s) {
                shift(sParent, s, s.right);//不可能是s.left因为代码如果能执行到这里，就只会有右孩子，因为s.left比s更小
                s.right = curNode.right;
            }
            //4.3后继节点取代被删除节点
            if (parentNode == null) {
                root = s;
            } else {
                shift(parentNode, curNode, s);
            }
            s.left = curNode.left;//之前没有左孩子，现在有左孩子，顶替掉的要长兄如父

        }
        return root;
    }

    //编写一个托孤方法
    //将待删除节点的孩子节点托付给父节点，顶替掉自己的位置
    private void shift(TreeNode parentNode, TreeNode deleteNode, TreeNode child) {
        if (deleteNode == parentNode.left) {
            parentNode.left = child;
        } else {
            parentNode.right = child;
        }
    }
}

669. Trim a Binary Search Tree

Medium

Given the root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lies in [low, high]. Trimming the tree should not change the relative structure of the elements that will remain in the tree (i.e., any node's descendant should remain a descendant). It can be proven that there is a unique answer.

Return the root of the trimmed binary search tree. Note that the root may change depending on the given bounds.

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) {
            return null;
        }
        while (root != null && (root.val < low || root.val > high)) {
            if (root.val < low) {
                root = root.right;
            } else if (root.val > high) {
                root = root.left;
            }
        }
        TreeNode cur = root;
        while(cur!=null) {
            while (cur.left != null && cur.left.val < low) {
                cur.left = cur.left.right;
            }
            cur = cur.left;
        }
        cur=root;
        while (cur!=null) {
            while (cur.right != null && cur.right.val > high) {
                cur.right = cur.right.left;
            }
            cur = cur.right;
        }
        return root;
    }
}
class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) {
            return null;
        }
        if (root.val < low) {
            return trimBST(root.right, low, high);
        }
        if (root.val > high) {
            return trimBST(root.left, low, high);
        }
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }
}

108. Convert Sorted Array to Binary Search Tree

Easy

Given an integer array nums where the elements are sorted in ascending order, convert it to a 

height-balanced

 binary search tree.

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        TreeNode root = traversal(nums, 0, nums.length - 1);
        return root;
    }
    private TreeNode traversal(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }
        int mid = (left + right) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = traversal(nums, left, mid - 1);
        root.right = traversal(nums, mid + 1, right);
        return root;
    }
}

538. Convert BST to Greater Tree

Medium

Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST.

As a reminder, a binary search tree is a tree that satisfies these constraints:

  • The left subtree of a node contains only nodes with keys less than the node's key.
  • The right subtree of a node contains only nodes with keys greater than the node's key.
  • Both the left and right subtrees must also be binary search trees.
class Solution {
    int pre = 0;
    int sum = 0;

    public TreeNode convertBST(TreeNode root) {
        inorderTraversal(root);
        return root;
    }

    private void inorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        inorderTraversal(root.right);
        sum = pre + root.val;
        pre = sum;
        root.val = sum;
        inorderTraversal(root.left);
    }
}
class Solution {
    public TreeNode convertBST(TreeNode root) {
         if (root == null) {
            return null;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        int sum = 0;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.right;
            } else {
                cur = stack.pop();
                sum = sum + cur.val;
                cur.val = sum;
                cur = cur.left;
            }
        }
        return root;
    }
}

阅读全部

相关推荐

最近更新

  4. TCP协议是安全的吗?

    2024-04-14 10:32:05       19 阅读

  12. 阿里云服务器执行yum，一直下载docker-ce-stable失败

    2024-04-14 10:32:05       19 阅读

  13. 【Python教程】压缩PDF文件大小

    2024-04-14 10:32:05       19 阅读

  18. 通过文章id递归查询所有评论（xml）

    2024-04-14 10:32:05       20 阅读

热门阅读

  5. 代码随想录-算法训练营day11【栈与队列02：有效的括号、删除字符串中的所有相邻重复项、逆波兰表达式求值】

    2024-04-14 10:32:05       18 阅读

  6. python中的正则表达式

    2024-04-14 10:32:05       13 阅读

  9. React EasyUI插件 学习笔记（基础）详细版

    2024-04-14 10:32:05       20 阅读

  13. 优先级队列 priority_queue 与 仿函数 greater / less

    2024-04-14 10:32:05       22 阅读

  14. vscode debug 配置：launch.json

    2024-04-14 10:32:05       16 阅读

  22. 谈谈springboot的工厂模式

    2024-04-14 10:32:05       18 阅读

  24. webrtc m98编译问题记录

    2024-04-14 10:32:05       47 阅读

  27. js的常用方法

    2024-04-14 10:32:05       20 阅读