做外账经常进哪几个网站,德州专业网站开发公司,推广商,网站到底备案好不好一、二叉搜索树的应用
1. 700【二叉搜索树中的搜索】
题目#xff1a; 给定二叉搜索树#xff08;BST#xff09;的根节点 root 和一个整数值 val。你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在#xff0c;则返回 null 。代码 给定二叉搜索树BST的根节点 root 和一个整数值 val。你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在则返回 null 。代码
class Solution {public TreeNode searchBST(TreeNode root, int val) {//二叉搜索树是有序的因此可以利用其特性进行搜索if(rootnull) return null;if(root.valval) return root;if(root.val val){root searchBST(root.left,val);}else {root searchBST(root.right,val);}return root;}
}2. 98【验证二叉搜索树】
题目 给你一个二叉树的根节点 root 判断其是否是一个有效的二叉搜索树。有效二叉搜索树定义如下 节点的左子树只包含 小于 当前节点的数。节点的右子树只包含 大于 当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。 代码
class Solution {public boolean isValidBST(TreeNode root) {//利用二叉搜索树的特征中序遍历二叉搜索树会得到一个递增的数组ListInteger inorder new LinkedList();traversal(root,inorder);for (int i 1; i inorder.size(); i) {if(inorder.get(i-1)inorder.get(i)){return false;}}return true;}public void traversal(TreeNode root,ListInteger inorder){if(root null) return;traversal(root.left,inorder);inorder.add(root.val);traversal(root.right,inorder);}
}3. 530【二叉搜索树的最小绝对差】
题目 给你一个二叉搜索树的根节点 root 返回树中任意两不同节点值之间的最小差值 。差值是一个正数其数值等于两值之差的绝对值。代码
class Solution {public int min Integer.MAX_VALUE;public TreeNode pre;public int getMinimumDifference(TreeNode root) {//仍旧利用二叉搜索树的中序遍历是递增的这个特性//在中序遍历的过程中记录最小差值同时记录上一个遍历的节点traversal(root);return min;}public void traversal(TreeNode root){if(root null) return;traversal(root.left);if(pre ! null){int sub Math.abs(pre.val-root.val);min submin ? min:sub;}pre root;traversal(root.right);}
}4. 501【二叉搜索树中的众数】
题目 给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回 新的头节点 。代码
class Solution {public TreeNode pre null;public int count 0;public int max 0;public int[] findMode(TreeNode root) {//二叉搜索树的中序遍历是递增的那么相同的树一定相邻//在中序遍历时记录当前遍历节点的上一个节点来比较是否相等ArrayListInteger list new ArrayList();traversal(root,list);int[] ansList new int[list.size()];for (int i 0; i list.size(); i) {ansList[i] list.get(i);}return ansList;}public void traversal(TreeNode root,ArrayListInteger list){if(root null) return;traversal(root.left, list);if(prenull || pre.val!root.val){count 1;}else{count;}if(count max){max count;list.clear();list.add(root.val);}else if(count max){list.add(root.val);}pre root;traversal(root.right,list);}
}5. 701【二叉搜索树中的插入操作】
题目 给定二叉搜索树BST的根节点 root 和要插入树中的值 value 将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 新值和原始二叉搜索树中的任意节点值都不同。 注意可能存在多种有效的插入方式只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。代码
class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {//BST中序遍历是有序的直接中序遍历二叉树遇到空节点插入即可if(root null){return new TreeNode(val);}if(root.valval){root.left insertIntoBST(root.left,val);}if(root.valval){root.right insertIntoBST(root.right,val);}return root;}
}6. 450【删除二叉搜索树中的节点】
题目 给定一个二叉搜索树的根节点 root 和一个值 key删除二叉搜索树中的 key 对应的节点并保证二叉搜索树的性质不变。返回二叉搜索树有可能被更新的根节点的引用。 一般来说删除节点可分为两个步骤 首先找到需要删除的节点如果找到了删除它。 代码
class Solution {public TreeNode deleteNode(TreeNode root, int key) {//分为五种情况//①未找到直接返回root//②找到的节点左子树为空右子树非空右子树补上//③找到的节点右子树为空左子树非空左子树补上//④找到的节点左右子树都为空直接删除//⑤找到的节点左右子树都非空左子树添加到右子树最左边右子树补上//或者右子树添加到左子树最右边左子树补上if(root null) return root;if(root.val key){if(root.leftnull root.right!null){return root.right;}else if(root.left!null root.rightnull){return root.left;}else if(root.leftnull root.rightnull){return null;}else{TreeNode node root.right;while (node.left!null){node node.left;}node.left root.left;return root.right;}}if(root.left!null) root.left deleteNode(root.left,key);if(root.right!null) root.right deleteNode(root.right,key);return root;}
}7. 669【修剪二叉搜索树】
题目 给你二叉搜索树的根节点 root 同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即如果没有被移除原有的父代子代关系都应当保留)。 可以证明存在 唯一的答案 。 所以结果应当返回修剪好的二叉搜索树的新的根节点。注意根节点可能会根据给定的边界发生改变。代码
class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {if(root null) return root;//分三种情况//在区间左边查找右子树//在区间右边查找左子树//在区间里边检查左右子树返回本身if(root.vallow){return trimBST(root.right,low,high);}else if(root.valhigh){return trimBST(root.left,low,high);}root.left trimBST(root.left,low,high);root.right trimBST(root.right,low,high);return root;}
}8. 108【将有序数组转换为二叉搜索树】
题目 给你一个整数数组 nums 其中元素已经按 升序 排列请你将其转换为一棵 高度平衡二叉搜索树。 高度平衡二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。代码
class Solution {public TreeNode sortedArrayToBST(int[] nums) {//要想构造一个平衡的BST就需要在数组的中间位置开始进行构造//[left,right)return traversal(nums,0,nums.length);}public TreeNode traversal(int[] nums, int left, int right){if(leftright){return null;}//避免溢出int mid left(right-left)/2;TreeNode node new TreeNode(nums[mid]);node.left traversal(nums,left,mid);node.right traversal(nums,mid1,right);return node;}
}9. 538【把二叉搜索树转换为累加树】
题目 给出二叉 搜索 树的根节点该树的节点值各不相同请你将其转换为累加树Greater Sum Tree使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。代码
class Solution {int sum 0;public TreeNode convertBST(TreeNode root) {//观察例子可以发现根据右中左的顺序遍历就可以获得累加值traversal(root);return root;}public void traversal(TreeNode root){if(root null) return;traversal(root.right);sum root.val;root.val sum;traversal(root.left);}
}二、树与回溯
1. 257【二叉树的所有路径】
题目 给你一个二叉树的根节点 root 按 任意顺序 返回所有从根节点到叶子节点的路径。 叶子节点 是指没有子节点的节点代码
class Solution {ListString ansList new ArrayList();public ListString binaryTreePaths(TreeNode root) {//由根到叶子节点的路径则需要前序遍历//每遍历一个节点就需把节点加入路径中if(root null) return new ArrayList();String path ;traversal(root,path);return ansList;}public void traversal(TreeNode root,String path){if(root.left null root.right null){path path root.val;ansList.add(path);return;}String s path root.val-;if(root.left ! null) traversal(root.left,s);if(root.right ! null) traversal(root.right,s);}
}2. 112【路径总和】
题目 给你二叉树的根节点 root 和一个表示目标和的整数targetSum 。判断该树中是否存在 根节点到叶子节点 的路径这条路径上所有节点值相加等于目标和 targetSum 。如果存在返回 true 否则返回 false 。代码
class Solution {HashSetInteger sums new HashSet();public boolean hasPathSum(TreeNode root, int targetSum) {if(root null) return false;traversal(root,0);if(sums.contains(targetSum)){return true;}return false;}public void traversal(TreeNode root, int sum){if(root.leftnull root.rightnull){sum root.val;sums.add(sum);return;}sum root.val;if(root.left!null) traversal(root.left,sum);if(root.right!null) traversal(root.right,sum);}
}3. 113【路径总和Ⅱ】
题目 给你二叉树的根节点root和一个整数目标和targetSum找出所有从根节点到叶子节点路径总和等于给定目标和的路径。代码
class Solution {ListListInteger ansList new ArrayList();ListInteger path new LinkedList();public ListListInteger pathSum(TreeNode root, int targetSum) {//有一个递归就需要有一个回溯if(root null) return new ArrayList();traversal(root,targetSum);return ansList;}public void traversal(TreeNode root, int targetSum){path.add(root.val);targetSum - root.val;if(root.leftnull root.rightnull){if(targetSum 0){ansList.add(new ArrayList(path));}return;}if(root.left ! null) {traversal(root.left,targetSum);path.removeLast();}if(root.right ! null) {traversal(root.right,targetSum);path.removeLast();}}
}4. 236【二叉树的最近公共祖先】
题目 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”代码
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {//找最近公共祖先就需要从下往上找也就是说要根据前序遍历二叉树//找到哪个节点就返回哪个节点//如果没找到就返回nullif(rootnull || rootp || rootq){return root;}TreeNode left lowestCommonAncestor(root.left,p,q);TreeNode right lowestCommonAncestor(root.right,p,q);if(leftnull right!null) return right;if(left!null rightnull) return left;if(leftnull rightnull) return null;return root;}
}5. 235【二叉搜索树的最近公共祖先】
题目 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。代码
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {//二叉搜索树的中序遍历是有序的所以p,q的最近公共祖先一定在[p,q]if(root null) return null;if(root.valp.val root.valq.val){TreeNode node lowestCommonAncestor(root.left,p,q);}if(root.valp.val root.valq.val){TreeNode node lowestCommonAncestor(root.right,p,q);}return root;}
}
