官方网站优化价格,wordpress 比特币插件,网址申请注册方法,学程序员大概要多少钱1.树相关题目
1.1 二叉树的中序遍历#xff08;简单#xff09;#xff1a;递归
题目#xff1a;使用中序遍历二叉树
思想#xff1a;按照访问左子树——根节点——右子树的方式遍历这棵树#xff0c;而在访问左子树或者右子树的时候我们按照同样的方式遍历#xff0…1.树相关题目
1.1 二叉树的中序遍历简单递归
题目使用中序遍历二叉树
思想按照访问左子树——根节点——右子树的方式遍历这棵树而在访问左子树或者右子树的时候我们按照同样的方式遍历直到遍历完整棵树 总结对于一棵树而言从根节点出发有左子树和右子树而对于左子树和右子树而言根节点下的第一个左子树节点可以看作一个新的根节点依次类推因此在树种大部分会使用到递归这个概念 代码定义 inorder(root) 表示当前遍历到 root 节点的答案
public class TreeNode{int val;TreeNode left;TreeNode right;TreeNode(){}TreeNode(int val){this.val val;}TreeNode(int val,TreeNode tight,TreeNode left){this.val val;this.left left;this.right right; }
}
class Solution{public ListInteger inorderTraversal(TreeNode root){ListInteger list new ArrayList();inorder(root,list);return list;}public void inorder(TreeNode root,ListInteger list){if(root null){return;}//遍历左子树inorder(root.left,list);//加入中间节点list.add(root.val);//遍历右子树inorder(root.right,list);}
} 1.2 不同的二叉搜索树Ⅰ中等动态规划
题目给一个节点求出有多少种不同的二叉搜索树
思想因此在生成所有可行的二叉搜索树的时候假设当前序列长度为 n如果我们枚举根节点的值为 i那么根据二叉搜索树的性质我们可以知道左子树的节点值的集合为 1…i−1[1…i−1]右子树的节点值的集合为 i1…n[i1…n]。使用动态规划来求解本题则根为 i 的所有二叉搜索树的集合是左子树集合和右子树集合的笛卡尔积对于笛卡尔积中的每个元素加上根节点之后形成完整的二叉搜索树
笛卡尔积笛卡尔积是一种数学运算它将两个集合的元素分别组合起来生成一个新的集合。新集合中的每个元素都是由两个集合中的一个元素组成的有序对其中第一个元素来自第一个集合第二个元素来自第二个集合。简单来说就是将两个集合中的元素进行组合生成所有可能的组合情况。
例如有两个集合A{1,2}和B{a,b}它们的笛卡尔积为{(1,a),(1,b),(2,a),(2,b)}。其中第一个元素为1或2第二个元素为a或b共有4种组合情况。 总结对于一组任意序列而言能够产生的二叉搜索树是很多的根据二叉搜索树的定义约束我们可以任意选用根节点然后选择根节点的左边和右边序列组成所有可能的左子树和右子树最终连接即可公式为 代码
class Solution {public int numTrees(int n) {//G为n1是为了存G[0]int[] G new int[n1];G[0] 1;G[1] 1;
//由于G[n] Σ(G[i -1]*G[n-i]);//将i当作n对应求和中的上限nfor(int i 2 ; i n; i){//将j当作i。对应求和中的遍历ifor(int j 1; j i ; j){G[i] G[j - 1] * G[i - j]; }}return G[n];}
} 1.3 不同的二叉搜索树Ⅱ中等回溯
题目给一个节点将这个节点有多少种二叉搜索树全部展示出来
思想二叉搜索树BST的性质为根节点的值大于左子树所有节点的值小于右子树所有节点的值且左子树和右子树也同样为二叉搜索树因此在生成所有可行的二叉搜索树的时候假设当前序列长度为 n如果我们枚举根节点的值为 i那么根据二叉搜索树的性质我们可以知道左子树的节点值的集合为 1…i−1[1…i−1]右子树的节点值的集合为 i1…n[i1…n]。而左子树和右子树的生成相较于原问题是一个序列长度缩小的子问题采用回溯的方法来解决这道题目 总结与第一题类似我们展示所有的二叉搜索树也可以选用不同的根节点将根节点两边序列分别递归得到左右子树组合为一个树即可 代码
public class TreeNode{int val;TreeNode left;TreeNode right;TreeNode(){}TreeNode(int val){this.val val;}TreeNode(int val,TreeNode tight,TreeNode left){this.val val;this.left left;this.right right; }
}
class Solution {public ListTreeNode generateTrees(int n) {if (n 0) {return new LinkedListTreeNode();}return generateTrees(1, n);}
public ListTreeNode generateTrees(int start, int end) {ListTreeNode allTrees new LinkedListTreeNode();if (start end) {allTrees.add(null);return allTrees;}
// 枚举可行根节点每一个都可以做根节点for (int i start; i end; i) {//用相同的方法做两次相同的行为// 获得所有可行的左子树集合ListTreeNode leftTrees generateTrees(start, i - 1);
// 获得所有可行的右子树集合ListTreeNode rightTrees generateTrees(i 1, end);
//将可行的左子树、右子树、根节点组合// 从左子树集合中选出一棵左子树从右子树集合中选出一棵右子树拼接到根节点上for (TreeNode left : leftTrees) {for (TreeNode right : rightTrees) {TreeNode currTree new TreeNode(i);currTree.left left;currTree.right right;allTrees.add(currTree);}}}return allTrees;}
} 1.4 验证二叉搜索树中等
题目给一个二叉树的根节点判断是否是有效的二叉搜索树
思想如果该二叉树的左子树不为空则左子树上所有节点的值均小于它的根节点的值 若它的右子树不空则右子树上所有节点的值均大于它的根节点的值它的左右子树也为二叉搜索树 总结二叉搜索树的性质是左边子树值均小于根节点右边子树值均大于根节点且其左右子树也满足该性质左右子树的判断进行递归即可此题的思想一样是利用根节点的左右两端小于/大于的情况生成判断isValidBST(root,Long.MIN_VALUE,Long.MAX_VALUE) 代码什么是递归就是大的用的方法小的也用到了那就一起用
class Solution {public boolean isValidBST(TreeNode root) {return isValidBST(root,Long.MIN_VALUE,Long.MAX_VALUE);}
public boolean isValidBST(TreeNode root,long lower,long upper){if(root null){return true;}if(root.val lower || root.val upper){return false;}
//对于root的左节点而言都小于根节点对于root的右节点而言都大于根节点return isValidBST(root.left,lower,root.val) isValidBST(root.right,root.val,upper);}
} 1.5 二叉树的层序遍历中等广度优先搜索队列
题目给你二叉树的根节点 root 返回其节点值的 层序遍历 。 即逐层地从左到右访问所有节点
思想创建一个队列从根节点开始入队出队然后是左右子节点入队出队如果队列不为空若队列长度为s则遍历s输出即可 总结使用队列的方式先将根节点入队然后让左右子节点以此入队出队即可先判断队列是否为空然后根据队列长度输出元素 代码
class Solution {public ListListInteger levelOrder(TreeNode root) {ListListInteger res new ArrayList();if(root null){return res;}//创建一个队列QueueTreeNode queue new LinkedList();queue.offer(root);//判断是否为空while(!queue.isEmpty()){ListInteger list new ArrayList();int len queue.size();//根据长度出队for(int i 1; i len; i){TreeNode currRoot queue.poll();if(currRoot.left ! null){queue.offer(currRoot.left);}if(currRoot.right ! null){queue.offer(currRoot.right);}list.add(currRoot.val);}res.add(list);}return res;}
} 1.6 相同的树简单深度优先搜索递归
题目给你两棵二叉树的根节点 p 和 q 编写一个函数来检验这两棵树是否相同
思想 判断是否为空 如果两个二叉树都为空则两个二叉树相同 如果两个二叉树中有且只有一个为空则两个二叉树一定不相同。 如果两个二叉树都不为空判断根节点与左右子树 那么首先判断它们的根节点的值是否相同若不相同则两个二叉树一定不同 若相同再分别判断两个二叉树的左子树是否相同以及右子树是否相同 这是一个递归的过程因此可以使用深度优先搜索递归地判断两个二叉树是否相同 总结判断树是否相同利用深度优先搜索判断是否都为空、根节点是否相同、子树是否相同 代码什么是递归就是大的用的方法小的也用到了那就一起用
什么是深度优先搜索从上往下依次搜索
lass Solution {public boolean isSameTree(TreeNode p, TreeNode q) {//是否为空if(p null q null){return true;}//是否只有一个为空else if(p null || q null){return false;}//根节点是否相同else if(p.val ! q.val){return false;}//左右子树是否相同else{return isSameTree(p.left,q.left) isSameTree(p.right,q.right);}}
} 1.7 从前序与中序遍历序列构造二叉树中等递归
题目给定两个整数数组 preorder 和 inorder 其中 preorder 是二叉树的前序遍历 inorder 是同一棵树的中序遍历请构造二叉树并返回其根节点。
思想只要我们在中序遍历中定位到根节点那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的因此我们就可以对应到前序遍历的结果中对上述形式中的所有左右括号进行定位 总结前序遍历和中序遍历都给出了所有树节点前序第一个节点就是根节点将其找到在中序遍历中就能得到根节点的左右子树节点的个数然后根据其个数将其递归组合为一个二叉树即可 代码
class Solution {private MapInteger, Integer indexMap;
public TreeNode buildTree(int[] preorder, int[] inorder) {int n preorder.length;// 构造哈希映射帮助我们快速定位根节点indexMap new HashMapInteger, Integer();for (int i 0; i n; i) {indexMap.put(inorder[i], i);}return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);}public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {if (preorder_left preorder_right) {return null;}
// 前序遍历中的第一个节点就是根节点int preorder_root preorder_left;// 在中序遍历中定位根节点int inorder_root indexMap.get(preorder[preorder_root]);// 先把根节点建立出来TreeNode root new TreeNode(preorder[preorder_root]);// 得到左子树中的节点数目int size_left_subtree inorder_root - inorder_left;// 递归地构造左子树并连接到根节点//先序遍历中「从 左边界1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素root.left myBuildTree(preorder, inorder, preorder_left 1, preorder_left size_left_subtree, inorder_left, inorder_root - 1);// 递归地构造右子树并连接到根节点// 先序遍历中「从 左边界1左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位1 到 右边界」的元素root.right myBuildTree(preorder, inorder, preorder_left size_left_subtree 1, preorder_right, inorder_root 1, inorder_right);return root;}
} 1.8 平衡二叉树简单自顶向下递归
题目给定一个二叉树判断它是否是高度平衡的二叉树 高度平衡一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 二叉树的高度其左右子树的最大高度1
思想一棵二叉树是平衡二叉树当且仅当其所有子树也都是平衡二叉树因此可以使用递归的方式判断二叉树是不是平衡二叉树递归的顺序可以是自顶向下或者自底向上 总结在做树的题时都要先将root null的情况一判断然后根据题目去求解比如平衡二叉树按照定义来做左右子树高度差小于等于1左右子树也都为平衡二叉树节点高度是左右子树最大高度 1 代码
class Solution {public boolean isBalanced(TreeNode root) {if(root null){return true;}//平衡二叉树//左右子树高度差 1 且 左右子树也均为平衡二叉树return Math.abs(height(root.left) - height(root.right)) 1 isBalanced(root.left) isBalanced(root.right);}
public int height(TreeNode root){if(root null){return 0;}//二叉树的高度为左右子树最大高度 1return Math.max(height(root.left),height(root.right)) 1;}
} 1.9 二叉树的最小深度简单深度优先搜索/广度优先搜索 递归
题目给定一个二叉树找出其最小深度最小深度是从根节点到最近叶子节点的最短路径上的节点数量
思想深度优先搜索 如果根节点为空返回0 如果只有根节点返回1 如果有左右子树则最小深度就是左右子树的最小深度 1 总结深度优先搜索可以将问题拆分为小问题然后利用递归来解决 代码
class Solution {public int minDepth(TreeNode root) {//如果没有根节点返回0if(root null){return 0;}
//如果只有根节点返回1if(root.left null root.right null){return 1;}
int min_Depth Integer.MAX_VALUE;//如果有子树分别比较左右子树深度哪个更小然后将其加1并返回if(root.left ! null){min_Depth Math.min(minDepth(root.left),min_Depth);}if(root.right ! null){min_Depth Math.min(minDepth(root.right),min_Depth);}
return min_Depth 1;}
} 1.10 二叉树展开为链表中等前序遍历
题目给你二叉树的根结点 root 请你将它展开为一个单链表; 展开后的单链表应该同样使用 TreeNode 其中 right 子指针指向链表中下一个结点而左子指针始终为 null 。 展开后的单链表应该与二叉树先序遍历顺序相同。
思想先前序遍历得到单链表的顺序然后将各节点的左节点指向null右节点指向下一个前序遍历中的节点 总结深度优先搜索可以将问题拆分为小问题然后利用递归来解决 代码
class Solution {public void flatten(TreeNode root) {//先拿到前序遍历后的节点(注意此时不是要值因此可以不用取树的值)作为单链表展开后的顺序ListTreeNode list new ArrayList();preorder(root,list);
//将单链表左节点设为null右节点赋为先序遍历的下一个值//这里长度为 list.size() - 1,因为倒数第二个节点可以有左右子节点但倒数第一个节点肯定是没有左右子节点的for(int i 0; i list.size() - 1; i){TreeNode prev list.get(i);prev.left null;prev.right list.get(i 1);}}
public void preorder(TreeNode root,ListTreeNode list){if(root null){return;}list.add(root);preorder(root.left,list);preorder(root.right,list);}
} 1.11 二叉树的最近公共祖先中等递归
题目给定一个二叉树, 找到该树中两个指定节点的最近公共祖先 最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”
思想两种情况 公共祖先不是自己 公共祖先是自己
因此可以先定义一个函数fx表示x节点的子树中是否包含p或者q 总结首先需要读懂题意然后才能入手解决这种较为复杂的问题可以设置一个专门判断是否存在节点p、q的函数从而根据两种情况递归的使用该函数最终得到结果 代码
class Solution {
//用来保存最近公共祖先private TreeNode res;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {isSon(root,p,q);return this.res;}
//定义一个函数用来检查root中是否包含p或者q是则返回true该方法无法直接找到公共祖先而是找到包含p或者q的节点public boolean isSon(TreeNode root,TreeNode p,TreeNode q){if(root null){return false;}//root的左子节点包含p或qboolean lson isSon(root.left,p,q);//root的右子节点包含p或者qboolean rson isSon(root.right,p,q);//如果root的左右子节点各包含了p、q说明root就是最近公共祖先节点if(lson rson){this.res root;}//如果root本身就是q或者q则root就是最近公共祖先if((root.val p.val || root.val q.val) (lson || rson)){this.res root;}//若左子树、右子树、节点本身就包含p或者q就返回truereturn lson || rson || (root.val p.val || root.val q.val);}
} 1.12 填充每个节点的下一个右侧节点指针中等层次遍历
题目给定一个 完美二叉树 其所有叶子节点都在同一层每个父节点都有两个子节点填充它的每个 next 指针让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点则将 next 指针设置为 NULL。
思想对二叉树进行层次遍历然后对其节点进行右侧指针连接 总结只需进行层次遍历便能够得到每个节点然后队列出队时只要不是倒数第一个元素就将队列头部元素赋给出队元素指针即可 代码
补充Java中Queue共有6个方法
1、offer函数和add函数的区别
在一个满的队列中加入一个新项多出的项就会被拒绝。 add() 在队列中添加元素若队列已满抛出 unchecked 异常 offer() :在队列中添加元素若队列已满返回 false。
2、poll函数和remove函数的区别
remove()从队列中删除第一个元素若集合为空返回异常
poll() 从队列中删除第一个元素若集合为空返回null
3、peek函数和element函数的区别
element() 在队列头部查询元素若集合为空返回异常
peek() 在队列头部查询元素若集合为空返回null
class Solution {public Node connect(Node root) {if(root null){return root;}
//创建队列用来进行层次遍历时的入队出队QueueNode queue new LinkedList();queue.add(root);
//循环先判断queue是否为空不为空则遍历queue所有元素出队操作while(!queue.isEmpty()){int len queue.size();for(int i 0; i len; i){
Node node queue.poll();
//在层序遍历中加入连接右侧指针操作if(i len - 1){//查询此时queue中的头部元素将其赋给node指针nextnode.next queue.peek();}
if(node.left ! null){queue.add(node.left);}if(node.right ! null){queue.add(node.right);}}}return root;}
} 1.13 二叉树的右视图中等深度优先搜索/广度优先搜索
题目给定一个二叉树的 根节点 root想象自己站在它的右侧按照从顶部到底部的顺序返回从右侧所能看到的节点值
思想对树进行深度优先搜索搜索过程中先访问右子树则第一个节点就是最右边的节点知道树的层数就能得到最终的结果数组 总结要注意当右侧没有节点时左子树节点的值也是右侧视图能够看到的节点 代码
class Solution {public ListInteger rightSideView(TreeNode root) {//创建存入右侧节点的数组ListInteger res new ArrayList();dfs(res, root, 0);return res;}
public void dfs(ListInteger res, TreeNode root, int level){if(root ! null){//只有在当前深度才能加入节点值if(res.size() level){res.add(root.val);}//右视图则先遍历右边节点然后将其插入数组dfs(res, root.right, level 1);//如果没有右节点那么左节点就是右侧视图的第一个节点dfs(res, root.left, level 1);}}
}
