wordpress关于本站,免费的做网站,腾讯云市场 wordpress,网站在工信部备案如何做#xff08;1#xff09;二叉树的前中后遍历
最基本的树的遍历#xff0c;不会可以重开了
public class Solution {/*** 代码中的类名、方法名、参数名已经指定#xff0c;请勿修改#xff0c;直接返回方法规定的值即可** * param root TreeNode类 * return int整型一维…1二叉树的前中后遍历
最基本的树的遍历不会可以重开了
public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param root TreeNode类 * return int整型一维数组*/public void preorder(ListInteger list, TreeNode root){// 先序遍历则先处理根节点list.add(root.val);if(root.left!null){preorder(list, root.left);}if(root.right!null){preorder(list, root.right);}}public int[] preorderTraversal (TreeNode root) {if(rootnull){return new int[0];}// write code hereListInteger tmpnew ArrayList();preorder(tmp, root);int [] resnew int[tmp.size()];for(int i0; ires.length; i){res[i]tmp.get(i);}return res;}
}前序遍历的顺序为 根-左-右中序为左-根-右后序为左-右-根因此这些遍历也可以说是先根、中根、后根遍历。 public void preorder(ListInteger list, TreeNode root){// 先序遍历则先处理根节点// list.add(root.val);if(root.left!null){preorder(list, root.left);}//list.add(root.val); 中序遍历if(root.right!null){preorder(list, root.right);}//list.add(root.val); 后续遍历}(2) 二叉树的最大深度
链接 不知道空间复杂度为O(1)的算法是什么…除非你修改树的数据结构因此这显然是不成立的。 首先可以用dfs来做空间复杂度为O(n),即为栈的高度。空间复杂度会为n是因为树可能只有一个分支。我们可以再写一个函数来完成dfs。即如果左子非空则向左dfs同时deep1.右子非空则向右dfs同时deep1. 最后查看max与deep的大小并且更改max。如果理解不了可以学习栈的知识以及递归是怎么做到的。
int max0;public void dfs(TreeNode root, int deep){if(root.left!null){dfs(root.left, deep1);}if(root.right!null){dfs(root.right, deep1);}if(maxdeep){maxdeep;} }public int maxDepth (TreeNode root) {// write code hereif(rootnull){return 0;}dfs(root,1);return max;}除此之外还可以用层序遍历即记录有多少层这样也可以得到最大深度。但空间复杂度一定不为O(1)而是O(n). 层序遍历需要单独记录一下每一层的元素这样可以判断何时遍历完一层。
public int maxDepth (TreeNode root) {if(rootnull){return 0;}int max0;// write code hereQueueTreeNode qnew LinkedList();q.add(root);while(!q.isEmpty()){int lenq.size();for(int i0; ilen; i){TreeNode tq.poll();if(t.left!null){q.add(t.left);}if(t.right!null){q.add(t.right);}}max;}return max;}3 二叉搜索树与双向链表
链接 不难发现二叉搜索树的中序遍历就是我们最终需要的顺序因此这题一定会和中序遍历扯上关系。我们的基本思路就是中序遍历即 public void inorder(ListInteger list, TreeNode root){if(root.left!null){preorder(list, root.left);}list.add(root.val); // 或者其他操作 if(root.right!null){preorder(list, root.right);}}重点问题是如何处理前驱和后继的指向。可以创建空节点pre前驱用当前节点的左指针指向pre而pre的右指针指向当前节点最后将pre指向当前节点。我们的这部分就是中序遍历的操作部分即上面代码的 其他操作。 我们的convert操作即为inorder遍历但不需要做任何操作。中序的节点操作即对我刚刚描述的内容的转义。
public class Solution {TreeNode prenull, headnull;public TreeNode Convert(TreeNode pRootOfTree) {if(pRootOfTreenull){return null;}Convert(pRootOfTree.left);// 开始找到头节点if(headnull){headpRootOfTree;prehead;}else{pRootOfTree.leftpre;pre.rightpRootOfTree;prepRootOfTree;}Convert(pRootOfTree.right);return head;}
}(4) 合并二叉树
链接 可以用递归来做如果t1为null则返回t2反之返回t1。每次都合并一次节点即可。
public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {if(t1null){return t2;}if(t2null){return t1;}// write code hereTreeNode headnew TreeNode(t1.valt2.val);head.leftmergeTrees(t1.left, t2.left);head.rightmergeTrees(t1.right, t2.right);return head;}
