网站没有建设好可以备案吗,wordpress首页底部模板修改,wordpress 短信登录密码,青岛网站开发费用今天在牛客网和力扣上带来了数据结构中二叉树的进阶练习题 1.二叉搜索树与双向链表———二叉搜索树与双向链表_牛客题霸_牛客网 (nowcoder.com)
2.二叉树遍历————二叉树遍历_牛客题霸_牛客网 (nowcoder.com)
3.二叉树的层序遍历————102. 二叉树的层序遍历 - 力扣LeetCode
4.二叉树的层序遍历————107. 二叉树的层序遍历 II - 力扣LeetCode
5.两个节点的最近公共祖先————236. 二叉树的最近公共祖先 - 力扣LeetCode
6.根据二叉树创建字符串————606. 根据二叉树创建字符串 - 力扣LeetCode
7.从前序和中序遍历构造二叉树————105. 从前序与中序遍历序列构造二叉树 - 力扣LeetCode
8.从中序和后序遍历构造二叉树————106. 从中序与后序遍历序列构造二叉树 - 力扣LeetCode
9.非递归二叉树的前序遍历————144. 二叉树的前序遍历 - 力扣LeetCode
1二叉搜索树与双向链表 描述 输入一棵二叉搜索树将该二叉搜索树转换成一个排序的双向链表。如下图所示 数据范围输入二叉树的节点数 0≤n≤10000≤n≤1000二叉树中每个节点的值 0≤val≤10000≤val≤1000 要求空间复杂度O(1)O(1)即在原树上操作时间复杂度 O(n)O(n) 注意: 1.要求不能创建任何新的结点只能调整树中结点指针的指向。当转化完成以后树中节点的左指针需要指向前驱树中节点的右指针需要指向后继 2.返回链表中的第一个节点的指针 3.函数返回的TreeNode有左右指针其实可以看成一个双向链表的数据结构 4.你不用输出双向链表程序会根据你的返回值自动打印输出 输入描述 二叉树的根节点 返回值描述 双向链表的其中一个头节点。 示例1 输入 abc##de#g##f###复制输出 c b e g d f a 思路说实话这题我觉得挺难的看解答才弄懂我们要创建的链表的顺序就是二叉树中序遍历的顺序所以我们用一个中序遍历的方法在遍历过程中记录我们前一个节点让当前节点也前一个节点像链表一样连起来。
public class Solution {public TreeNode Convert(TreeNode pRootOfTree) {TreeNode a inOrderTree(pRootOfTree);return a;}public static TreeNode headnull;public static TreeNode prevnull;public static TreeNode inOrderTree(TreeNode root){if(rootnull){return null;}inOrderTree(root.left);if(prevnull){head root;prev root;}else{prev.right root;root.left prev;prev root;}inOrderTree(root.right);return head;}
}我们来走一遍 刚开始head和prev都为空我们进行中序遍历从节点10开始向左递归到节点6向左递归到节点4向左递归到null返回我们此时判断prev是否为空为空我们把head和prev都设立为当前节点4我们向右递归为空返回4全递归完毕整体返回到66的左节点递归完毕进行prev判断不为空prev的right指向当前节点当前节点的left指向前一个节点向右递归到8节点8节点向左递归为空返回判断prev不为空我们prev已经记录下前一个节点了让当前节点的left指向前一个节点前一个节点的right指向下一个当前节点我们就完成了两个节点的链接8向右递归遇到null返回6整体返回到10接下来重复这个过程。
注意1一定是对前一个节点进行操作如果提前对后一个节点进行操作那么就会丢失二叉树就找不到节点了。
2二叉树遍历 描述 编一个程序读入用户输入的一串先序遍历字符串根据此字符串建立一个二叉树以指针方式存储。 例如如下的先序遍历字符串 ABC##DE#G##F### 其中“#”表示的是空格空格字符代表空树。建立起此二叉树以后再对二叉树进行中序遍历输出遍历结果。 输入描述 输入包括1行字符串长度不超过100。 输出描述 可能有多组测试数据对于每组数据 输出将输入字符串建立二叉树后中序遍历的序列每个字符后面都有一个空格。 每个输出结果占一行。 示例1 输入 abc##de#g##f###复制输出 c b e g d f a 思路这道题我们要遍历字符串因为是用先序遍历的方法所以我们遇到字母的时候就创建节点##的时候就为空再对我们创建好的二叉树进行中序遍历。
import java.util.Scanner;class TreeNode{char val;TreeNode left;TreeNode right;public TreeNode(char val){this.val val;}
}
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);while(in.hasNextLine()){String str in.nextLine();TreeNode root createTree(str);inorderTree(root);}}static int i 0;public static TreeNode createTree(String str){TreeNode b null;char a str.charAt(i);if(a!#){b new TreeNode(a);i;b.leftcreateTree(str);b.rightcreateTree(str);}else{i;return null;}return b;}public static void inorderTree(TreeNode root){if(rootnull){return ;}inorderTree(root.left);System.out.print(root.val );inorderTree(root.right);}
}
创建节点和中序遍历的方法就不说了前几期都详细介绍了嗷我们直接讲那个创建二叉树还是刚才那样一步一步来。 int i我们定义成为静态的因为我们递归的时候不希望他返回的时候没有进行操作定义静态的就不受影响了我们从字符串开始看我们开始i为1得到的第一个字符是aa不等于#我们创建节点Ai节点的左边我们开始递归字符不为#创建节点i这个节点此时已经与A的左边连上了我们继续向左递归字符不为#i创建节点c与b的左边连上再向左递归遇到nulli返回null此时来到c的左边c向右递归遇到井号i返回null返回到bb向右递归............一直下去。
3二叉树的层序遍历 给你二叉树的根节点 root 返回其节点值的 层序遍历 。 即逐层地从左到右访问所有节点。 示例 1 输入root [3,9,20,null,null,15,7]
输出[[3],[9,20],[15,7]]示例 2 输入root [1]
输出[[1]]示例 3 输入root []
输出[]思路这题不难的我们之前详细做过二叉树的层序遍历我们只要用一个引用和一个队列就OK了但是这题不一样他想让我们返回一个类似二维数组的链表 我们只需要之前层序遍历打印元素的时候提前算出我们要放在每一层的元素个数再把他们都放到小链表中最后再放到大链表中。
class Solution {QueueTreeNode queue new LinkedListTreeNode();ListListInteger list1 new LinkedList();public ListListInteger levelOrder(TreeNode root) {if(rootnull){return list1;}TreeNode cur root;queue.offer(root);while(!queue.isEmpty()){ListInteger list2 new LinkedList();int sz queue.size();for(int i1;isz;i){cur queue.poll();list2.add(cur.val);if(cur.left!null){queue.offer(cur.left);}if(cur.right!null){queue.offer(cur.right);}}list1.add(list2);}return list1;}
}
4二叉树的层序遍历2 给你二叉树的根节点 root 返回其节点值 自底向上的层序遍历 。 即按从叶子节点所在层到根节点所在的层逐层从左向右遍历 示例 1 输入root [3,9,20,null,null,15,7]
输出[[15,7],[9,20],[3]]示例 2 输入root [1]
输出[[1]]示例 3 输入root []
输出[] 思路跟刚才的题基本一致只需要改一个地方我们已经实现了刚才的二维链表了我们在每次实现小链表的思路不变只需要在实现大链表的时候实现的不是尾插而是头插即可。
class Solution {QueueTreeNode queue new LinkedList();ListListInteger list1 new ArrayList();public ListListInteger levelOrderBottom(TreeNode root) {if(rootnull){return list1;}TreeNode cur null;queue.offer(root);while(!queue.isEmpty()){int sz queue.size();ListInteger list2 new ArrayList();while(sz0){cur queue.poll();list2.add(cur.val);sz--;if(cur.left!null){queue.offer(cur.left);}if(cur.right!null){queue.offer(cur.right);}}list1.add(0,list2);}return list1;}
}
5两个节点的最近公共祖先 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。” 示例 1 输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 1
输出3
解释节点 5 和节点 1 的最近公共祖先是节点 3 。示例 2 输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 4
输出5
解释节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。示例 3 输入root [1,2], p 1, q 2
输出1 这道题我们可以使用两个方法第一个就是传统的二叉树遍历第二个方法就是找他们的交点
第一种方法思路我们去遍历这个二叉树从左树开始完了右树我们可以分为4种情况。 p或者q就在树的根节点此时根节点直接就是我们要找的祖先节点。 第二种情况就是p和q在左树和右树的两边当二叉树从左到右全部递归完毕的时候我们走到节点此时判断leftNode和rightNode是否为空如果不为空说明当前节点已经是p,q节点的最近公共祖先了我们只需一直返回它即可这种情况一定是根节点
那这个只能判断根节点那么这个图怎么弄呢 我们在5节点找到最近公共祖先返回5节点3节点左边接收到5节点但是右边为null无法输出所以我们在最后两行判断了这种特殊情况如果只有左节点或者只有有节点成功获得祖先节点的返回值我们就输出获得的这个节点因为我们知道如果3的左边没有获得q节点那么它一定是在左边且p节点的下边因为题目说了一定有pq节点的。
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(rootnull){return root;}if(root.valp.val || root.valq.val){return root;}TreeNode leftNode lowestCommonAncestor(root.left,p,q);TreeNode rightNode lowestCommonAncestor(root.right,p,q);if(leftNode!null rightNode!null){return root;}if(leftNode!null){return leftNode;}return rightNode;}
} 第二种方法我们想象成两个链表相交的思路 我们遍历二叉树把p和q的长度放到对应的栈中 再让长的那个栈出一个元素之后两个栈一起出最后剩的一个元素就是我们的最近公共祖先。
class Solution {StackTreeNode stack1 new Stack();StackTreeNode stack2 new Stack();public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(rootnull){return null;}getpath(root,p,stack1);getpath(root,q,stack2);if(stack1.size()stack2.size()){StackTreeNode tmp new Stack();tmp stack1;stack1 stack2;stack2 tmp;}while(stack2.size()-stack1.size()0){stack2.pop();}while(stack1.peek().val ! stack2.peek().val){stack1.pop();stack2.pop();}return stack2.pop();}public boolean getpath(TreeNode root,TreeNode p,StackTreeNode stack){if(rootnull){return false;}stack.push(root);if(root.valp.val){return true;}boolean a getpath(root.left,p,stack);if(atrue){return true;}boolean b getpath(root.right,p,stack);if(btrue){return true;}stack.pop();return false;}
}
我们看着这个getpath代码走几次就拿题目中的p5q1 和p5q4。 我们找q节点
我们从节点3开始将节点3放入stack1中向左递归到5节点将5放到stack1中向左递归到节点6将节点6放到stack1中向左递归返回null向右递归返回null将节点6移出stack中返回5节点5节点向右递归到2节点将2节点放入stack1中向左递归遇到节点7将节点7放到stack中向左递归遇到null返回向右递归遇到null返回将7移出stack返回到节点2向右递归遇到节点4找到q节点了返回true到2节点返回true到5返回true到3的左边返回true找到q节点p节点同理当q1的时候左边没有一个true全部都被移出了。
6根据二叉树创建字符串 给你二叉树的根节点 root 请你采用前序遍历的方式将二叉树转化为一个由括号和整数组成的字符串返回构造出的字符串。 空节点使用一对空括号对 () 表示转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。 示例 1 输入root [1,2,3,4]
输出1(2(4))(3)
解释初步转化后得到 1(2(4)())(3()()) 但省略所有不必要的空括号对后字符串应该是1(2(4))(3) 。示例 2 输入root [1,2,3,null,4]
输出1(2()(4))(3)
解释和第一个示例类似但是无法省略第一个空括号对否则会破坏输入与输出一一映射的关系。 思路这道题就不是很难了我们观察每个输入输出的例子对于每个节点有几个子节点就会在后面出现对应节点null也为所以的父亲节点都会在的前面。
class Solution {public static StringBuilder sb;public String tree2str(TreeNode root) {sb new StringBuilder();createString(root);String str sb.toString();return str;}public void createString(TreeNode root){if(rootnull){return;}sb.append(root.val);if(root.left!null){sb.append(();createString(root.left);sb.append());}else{if(root.rightnull){return;}else{sb.append(();sb.append());}}if(root.right!null){sb.append(();createString(root.right);sb.append());}else{return;}}
}
这道题我们用子问题思路关注每个节点每次递归时我们都先把当前节点拼接到字符串上我们使用StringBuilder来拼接而不是用string去因为在使用String的时候会创建很多的对象浪费很多的内存和时间我们拼接好后判断当前节点左右子节点的情况在对其进行操作。
7前序遍历与中序遍历构造二叉树 给定两个整数数组 preorder 和 inorder 其中 preorder 是二叉树的先序遍历 inorder 是同一棵树的中序遍历请构造二叉树并返回其根节点。 示例 1: 输入: preorder [3,9,20,15,7], inorder [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]示例 2: 输入: preorder [-1], inorder [-1]
输出: [-1] 思路 我们是怎么通过先序遍历和中序遍历构建字符串的呢我们先看前序遍历因为前序遍历每次都是先遇到节点再向左向右遍历。所以我们创建二叉树的时候也是按照前序遍历的顺序构建节点接下来就要考虑节点的左右了我们这时使用中序遍历把中序遍历的头记为begin尾记为end我们先找跟节点前序遍历的头在中序遍历中找到前序遍历的头就是我们的根节点我们把它的下标记为index。 这时我们再分两边构建两树左边的begin不变end变味index-1右边end不变beginindex1 继续递归。 此时左树的end已经小于begin左树的递归就停止了右树继续 右树的左子树递归完毕beginend递归右子 递归全部完毕。
class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {return buildTreeChild(preorder,inorder,0,inorder.length-1);}int i 0;public TreeNode buildTreeChild(int[] preorder, int[] inorder, int begin, int end){if(beginend){return null;}TreeNode root new TreeNode(preorder[i]);int index FindIndex(preorder,inorder,begin,end);i;root.left buildTreeChild(preorder,inorder,begin,index-1);root.right buildTreeChild(preorder,inorder,index1,end);return root;}public int FindIndex(int[] preorder,int[] inorder, int begin,int end){for(int j begin;jend;j){if(preorder[i]inorder[j]){return j;}}return -1;}
} 8从中序与后序遍历构建二叉树 给定两个整数数组 inorder 和 postorder 其中 inorder 是二叉树的中序遍历 postorder 是同一棵树的后序遍历请你构造并返回这颗 二叉树 。 示例 1: 输入inorder [9,3,15,20,7], postorder [9,15,7,20,3]
输出[3,9,20,null,null,15,7]示例 2: 输入inorder [-1], postorder [-1]
输出[-1] 思路和刚才前序遍历加中序遍历构建二叉树一样。但是我们这次是从后序遍历最后一个下边往前遍历创建节点 在每次递归时我们都是先创建右树在左树。
class Solution {public int i;public TreeNode buildTree(int[] inorder, int[] postorder) {i postorder.length-1;return buildTreeChild(inorder,postorder,0,inorder.length-1);}public TreeNode buildTreeChild(int[] inorder,int[] postorder,int begin,int end){if(beginend){return null;}TreeNode root new TreeNode(postorder[i]);int index findIndex(inorder,postorder,begin,end);i--;root.right buildTreeChild(inorder,postorder,index1,end);root.left buildTreeChild(inorder,postorder,begin,index-1);return root;}public int findIndex(int[] inorder,int[] postorder,int begin,int end){for(int jbegin;jend;j){if(postorder[i]inorder[j]){return j;}}return -1;}
}
9非递归的二叉树的前序遍历 给你二叉树的根节点 root 返回它节点值的 前序 遍历。 示例 1 输入root [1,null,2,3] 输出[1,2,3] 解释 示例 2 输入root [1,2,3,4,5,null,8,null,null,6,7,9] 输出[1,2,4,5,6,7,3,8,9] 解释 示例 3 输入root [] 输出[] 示例 4 输入root [1] 输出[1] 这题我们之前做过我们使用最基础的递归我们可不可以用迭代做呢 既然是官方给的那必须做了。
我们之前用队列实现过层序遍历其实原理都一样我们这次使用栈来完成前序遍历。 看这个图我们把一放到栈中再把栈中的第一个元素pop到cur中。 把cur右边的元素先放到栈再放cur左边的栈。再出栈中的第一个元素如此往复。
class Solution {StackTreeNode stack1 new Stack();ListInteger list new LinkedList();public ListInteger preorderTraversal(TreeNode root) {if(rootnull){return list;}TreeNode cur null;stack1.push(root);while(!stack1.isEmpty()){cur stack1.pop();if(curnull){continue;}else{list.add(cur.val);stack1.push(cur.right);stack1.push(cur.left);}}return list;}
}
