[Java/数据结构]二叉树练习题几则

画师竹取工坊大佬们好我是Mem0rin现在正在准备自学转码。如果我的文章对你有帮助的话欢迎关注我的主页Mem0rin欢迎互三一起进步文章目录一、前序中序 或 后序中序求二叉树二、两个节点的最近祖先1. 递归2. 非递归三、二叉树的遍历构造挑了点我不是很熟悉的题目进行宣讲自己巩固一下希望有所帮助。一、前序中序 或 后序中序求二叉树Leetcode链接给定两个整数数组 preorder 和 inorder 其中 preorder 是二叉树的先序遍历 inorder 是同一棵树的中序遍历请构造二叉树并返回其根节点。我们采用递归的方式进行实现。思路和之前做小题的思路是相同的只需要从前序节点中找到根节点的位置然后在中序节点中找到根节点并把根节点的索引前后切割成左右子树再对左树和右树的数组分别递归处理。首先来实现找到根节点的功能根节点可以通过前序节点来确定那么需要做的就是找到对应的中序节点的位置。我们用findVal方法来实现publicintfindVal(intval,int[]inorder){inti0;for(;iinorder.length;i){if(inorder[i]val){returni;}}returni;}为了切割根节点前后的数组我们采用索引指定范围的方法用indexBegin指定树的左边界indexEnd指定右边界index指定根节点的位置那么我们就可以给出递归实现树的构造的框架。publicTreeNodebuildTree(int[]inorder,int[]preorder,intindexBegin,intindexEnd){if(indexBeginindexEnd){returnnull;}// int val ...TreeNodenodenewTreeNode(val);intinIndexfindVal(val,inorder);node.leftbuildTree(inorder,preorder,indexBegin,inIndex-1);node.rightbuildTree(inorder,preorder,inIndex1,indexEnd);returnnode;}但现在我们面临一个问题就是我们如何从前序遍历中读取根节点呢从前往后就行但是为了让读取的进程不被递归重置我们只能把指向前序遍历的索引设置为成员变量。这下我们可以把整个代码完善出来了。classSolution{publicintfindVal(intval,int[]inorder){inti0;for(;iinorder.length;i){if(inorder[i]val){returni;}}returni;}publicintpreIndex;publicTreeNodebuildTree(int[]inorder,int[]preorder,intindexBegin,intindexEnd){if(indexBeginindexEnd){returnnull;}intvalpreorder[preIndex];TreeNodenodenewTreeNode(val);preIndex;intinIndexfindVal(val,inorder);node.leftbuildTree(inorder,preorder,indexBegin,inIndex-1);node.rightbuildTree(inorder,preorder,inIndex1,indexEnd);returnnode;}publicTreeNodebuildTree(int[]preorder,int[]inorder){preIndex0;returnbuildTree(inorder,preorder,0,preorder.length-1);}}后序遍历同理但是需要注意的是有以下几点不同后序遍历是从后往前寻找根节点的。因为是从后往前遍历因此构造子树的顺序也是先构造右树再构造左树。二、两个节点的最近祖先Leetcode链接给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”我们采用递归和非递归两种方法进行解决1. 递归我们的前提是p和q都在树内。那么就会有以下三种情况p或q在树的根节点上p和q在树的两侧p和q在树的同侧前两个情况的最近祖先都是root第三种情况只需要继续往下递归直到出现上面两种情况即可。publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){if(rootnull){returnnull;}if(rootp||rootq){returnroot;}TreeNodeleftRootlowestCommonAncestor(root.left,p,q);TreeNoderightRootlowestCommonAncestor(root.right,p,q);if(leftRoot!nullrightRoot!null){returnroot;}returnleftRootnull?rightRoot:leftRoot;}2. 非递归我们使用栈的数据结构实现思想和“找到两个链表的交点”类似但是区别在于二叉树是非线性的因此只是记录节点之间的距离是不够的而是需要保存下来从根节点到对应节点的路径。我们对此的思路是采用前序遍历遍历到的节点都入栈如果入栈的节点左右都没有找到则出栈。publicStackTreeNodefindNode(TreeNoderoot,TreeNodep){StackTreeNodestacknewStack();TreeNodecurroot;TreeNodeprevnull;while(cur!null||!stack.isEmpty()){while(cur!null){stack.push(cur);if(curp){System.out.println(Find it);returnstack;}curcur.left;}TreeNodetopstack.peek();if(top.rightnull||top.rightprev){stack.pop();prevtop;}else{curtop.right;}}returnstack;}publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){StackTreeNodestack1findNode(root,p);StackTreeNodestack2findNode(root,q);intsize1stack1.size();System.out.println(size1 size1);intsize2stack2.size();System.out.println(size2 size2);while(size1size2){stack1.pop();size1--;}while(size2size1){stack2.pop();size2--;}while(stack1.peek()!stack2.peek()){stack1.pop();stack2.pop();}returnstack1.pop();}三、二叉树的遍历构造nowcoder链接读入用户输入的一串先序遍历字符串根据此字符串建立一个二叉树以指针方式存储。 例如如下的先序遍历字符串 ABC##DE#G##F### 其中“#”表示的是空格空格字符代表空树。建立起此二叉树以后再对二叉树进行中序遍历输出遍历结果。难度有点小大关键在于如何用 “#” 去确定二叉树的形状。明显的思路是如果遍历到的字符不为 “#” 则继续往下递归如果为 “#”则返回null。简单的代码如下if(c!#){TreeNoderootnewTreeNode(c);root.leftcreateTree(str);root.rightcreateTree(str);}else{returnnull}returnroot;之后就是字符串遍历的问题和上面的前序中序构建二叉树的时候遍历前序的方法一样我们同样构建一个成员变量用于指向字符串遍历到的位置。中序遍历在上一篇博客有说明不再赘述。具体实现如下staticinti;publicstaticTreeNodecreateTree(Stringstr){TreeNoderootnull;if(istr.length()){charcstr.charAt(i);i;if(c!#){rootnewTreeNode(c);root.leftcreateTree(str);root.rightcreateTree(str);}}returnroot;}// 中序遍历staticvoidinOrder(TreeNoderoot){if(rootnull){return;}inOrder(root.left);System.out.print(root.val);System.out.print( );inOrder(root.right);}publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);while(in.hasNext()){i0;Stringstrin.nextLine();TreeNodenodecreateTree(str);inOrder(node);}}如果题目没有给出main方法只需要再写一个方法把i封装进去就好。