文章目录1. 二叉搜索树与双向链表BM30题目描述解题思路代码示例2. 二叉树遍历KY11题目描述解题思路代码示例3. 二叉树的层序遍历LC102题目描述解题思路代码示例4. 二叉树的公共祖先(LC236)题目描述解题思路思路一思路二代码示例5. 从前序和中序遍历序列构建二叉树LC105题目描述解题思路代码示例6. 从中序和后序遍历序列构建二叉树LC106题目描述解题思路代码示例7. 根据二叉树创建字符串LC606题目描述解题思路代码示例8. 非递归法前序遍历LC1449. 非递归法中序遍历LC9410. 非递归法后序遍历LC1451. 二叉搜索树与双向链表BM30二叉搜索树与双向链表题目描述解题思路题目要求返回一个固定节点而递归调用是多次的所以要分成两个方法。ConvertChild搜索二叉树的特点是中序遍历得到的结果是有序的所以要采用中序遍历。prev来记录前一个节点。prev必须是类变量不可以是局部变量因为递归调用会重复把prev置空。转换成双向链表left和right就代表逻辑链表节点上的左右。当前节点的left置为prevprev不为空的情况下的right置为root。prev置为root此时题目给的pRootOfTree是链表的中心把head移到链表左端并返回代码示例publicclassSolution{TreeNodeprevnull;publicTreeNodeConvert(TreeNodepRootOfTree){if(pRootOfTreenull)returnnull;ConvertChild(pRootOfTree);TreeNodeheadpRootOfTree;while(head.left!null)headhead.left;returnhead;}publicvoidConvertChild(TreeNoderoot){if(rootnull)return;ConvertChild(root.left);if(prev!null)prev.rightroot;root.leftprev;prevroot;ConvertChild(root.right);}}2. 二叉树遍历KY11二叉树遍历题目描述解题思路createTree:遍历字符串因为函数要循环调用字符串要依次遍历所以下标i应该是类变量而非局部变量。如果字符不是#则创建新节点i自增接着创建左树和右树如果字符是#则i自增不创建节点。此时root还是null返回上一个函数。main函数先调用createTree再中序遍历二叉树输出字符为了防止牛客网给出多组测试字符串造成i过大i要手动置为0代码示例publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);while(in.hasNext()){Stringstrin.nextLine();TreeNodenodecreateTree(str);inOrder(node);i0;}}publicstaticinti0;staticTreeNodecreateTree(Stringstr){TreeNoderootnull;if(str.charAt(i)!#){rootnewTreeNode(str.charAt(i));i;root.leftcreateTree(str);root.rightcreateTree(str);}elsei;returnroot;}staticvoidinOrder(TreeNoderoot){if(rootnull)return;inOrder(root.left);System.out.print(root.val );inOrder(root.right);}}3. 二叉树的层序遍历LC102二叉树的层序遍历题目描述解题思路当队列不为空时循环处理每一层先获取当前队列大小即当前层的节点数量创建一个临时列表存储当前层的节点值循环取出当前层的所有节点循环次数为当前层节点数取出队首节点将其值加入临时列表如果该节点有左子节点将左子节点入队如果该节点有右子节点将右子节点入队当前层处理完毕后将临时列表加入结果列表代码示例publicListListIntegerlevelOrder(TreeNoderoot){ListListIntegerretnewArrayList();if(rootnull)returnret;QueueTreeNodequeuenewLinkedList();queue.offer(root);while(!queue.isEmpty()){intsizequeue.size();ListIntegerlistnewArrayList();while(size!0){TreeNodecurqueue.poll();list.add(cur.val);if(cur.left!null)queue.offer(cur.left);if(cur.right!null)queue.offer(cur.right);size--;}ret.add(list);}returnret;}4. 二叉树的公共祖先(LC236)二叉树的公共祖先题目描述解题思路思路一可以分成三种情况根节点root就是p或q 直接返回rootp和q分别在左树和右树p和q都在左树或都在右树分别定义 leftTree rightTree 在子树中遍历如果两个都不是空证明pq在左右两侧那么root就是最小公共祖先如果其中一个为空证明pq在同一侧返回已找到的公共祖先。思路二利用栈存储从根节点到p和q的路径找公共节点getPath先让root入栈如果node是root返回true接着在左右子树寻找路径如果左右子树中都没有说明当前节点不是到达node的经过的节点出栈。代码示例思路一publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){if(rootnull)returnnull;if(proot||qroot)returnroot;TreeNodeleftTreelowestCommonAncestor(root.left,p,q);TreeNoderightTreelowestCommonAncestor(root.right,p,q);if(leftTree!nullrightTree!null)returnroot;elseif(leftTree!null)returnleftTree;elsereturnrightTree;}思路二booleangetPath(TreeNodenode,TreeNoderoot,StackTreeNodestack){if(rootnull)returnfalse;stack.push(root);if(rootnode)returntrue;booleanretgetPath(node,root.left,stack);if(ret)returntrue;retgetPath(node,root.right,stack);if(ret)returntrue;stack.pop();returnfalse;}publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){if(rootnull)returnnull;StackTreeNodes1newStack();StackTreeNodes2newStack();getPath(p,root,s1);getPath(q,root,s2);intsize1s1.size();intsize2s2.size();if(size1size2){intsizesize1-size2;while(size!0){s1.pop();size--;}}else{intsizesize2-size1;while(size!0){s2.pop();size--;}}while(!s1.isEmpty()){TreeNodetmp1s1.pop();TreeNodetmp2s2.pop();if(tmp1tmp2){returntmp1;}}returnnull;}5. 从前序和中序遍历序列构建二叉树LC105从前序和中序遍历序列构建二叉树题目描述解题思路为了便于递归下标参数的传递另写一个函数。前序遍历确定根节点所以先创建根节点在中序数组中找到根节点值的下标下一次传参时创建左树的右边界就是preIndex-1创建右树的左边界就是preIndex1。代码示例intpreIndex;publicTreeNodebuildTree(int[]preorder,int[]inorder){returnbuildTreeChile(preorder,inorder,0,inorder.length-1);}publicTreeNodebuildTreeChile(int[]preorder,int[]inorder,intinBegin,intinEnd){if(inBegininEnd)returnnull;TreeNoderootnewTreeNode(preorder[preIndex]);introotIndexgetIndex(preorder[preIndex],inorder,inBegin,inEnd);preIndex;root.leftbuildTreeChile(preorder,inorder,inBegin,rootIndex-1);root.rightbuildTreeChile(preorder,inorder,rootIndex1,inEnd);returnroot;}intgetIndex(intval,int[]inorder,intinBegin,intinEnd){for(intiinBegin;iinEnd;i){if(inorder[i]val)returni;}return-1;}6. 从中序和后序遍历序列构建二叉树LC106从中序和后序遍历序列构建二叉树题目描述解题思路与上一题的解法类似。需要注意的是后序遍历的顺序是左 右 根所以要在后序数组中从后往前遍历先确定根节点再创建右树再创建左子树。代码示例intpostIndex;publicTreeNodebuildTree(int[]inorder,int[]postorder){postIndexpostorder.length-1;returnbuildTreeChild(inorder,postorder,0,inorder.length-1);}publicTreeNodebuildTreeChild(int[]inorder,int[]postorder,intinBegin,intinEnd){if(inBegininEnd)returnnull;TreeNoderootnewTreeNode(postorder[postIndex]);introotIndexgetIndex(postorder[postIndex],inorder,inBegin,inEnd);postIndex--;root.rightbuildTreeChild(inorder,postorder,rootIndex1,inEnd);root.leftbuildTreeChild(inorder,postorder,inBegin,rootIndex-1);returnroot;}intgetIndex(intval,int[]inorder,intinBegin,intinEnd){for(intiinBegin;iinEnd;i){if(inorder[i]val)returni;}return-1;}7. 根据二叉树创建字符串LC606根据二叉树创建字符串题目描述解题思路为了方便函数递归传参新写一个函数。先添加root的值再判断左树如果左树不为空添加左括号递归调用添加左数的值添加右括号如果左树为空再判断此时右树右树如果也为空就可以直接返回如果右树不为空那么左树的括号不能省略。再单独判断右树如果右树不为空与左树类似先添加左括号再递归调用再添加右括号代码示例publicStringtree2str(TreeNoderoot){StringBuilderretnewStringBuilder();tree2strChild(root,ret);returnret.toString();}voidtree2strChild(TreeNoderoot,StringBuilders){if(rootnull)return;s.append(root.val);if(root.left!null){s.append(();tree2strChild(root.left,s);s.append());}else{if(root.right!null)s.append(());elsereturn;}if(root.right!null){s.append(();tree2strChild(root.right,s);s.append());}}8. 非递归法前序遍历LC144非递归法前序遍历左子树内层循环当cur不为空时将其入栈并访问然后移动cur到其左子节点继续上述操作这个过程实现了 “根 - 左” 的访问顺序直到左子树尽头右子树处理当左子树遍历完成cur为空弹出栈顶节点top将cur指向top的右子节点此时外层循环会继续处理右子树重复左子树的遍历逻辑voidpreOrder(TreeNoderoot){TreeNodecurroot;StackTreeNodestacknewStack();while(cur!null||!stack.isEmpty()){while(cur!null){stack.push(cur);System.out.println(cur.val );curcur.left;}TreeNodetopstack.pop();curtop.right;}}9. 非递归法中序遍历LC94非递归法中序遍历与前序遍历类似区别在于中序遍历先访问左树所以要在内层循环结束也就是到左子树尽头再弹出并访问voidinOrder(TreeNoderoot){TreeNodecurroot;StackTreeNodestacknewStack();while(cur!null||!stack.isEmpty()){while(cur!null){stack.push(cur);curcur.left;}TreeNodetopstack.pop();System.out.println(top.val );curtop.right;}}10. 非递归法后序遍历LC145OJ 非递归法后序遍历后序遍历要先保证右树遍历后再访问根所以在输出根之前先判断右树是否为空如果为空输出根节点并把根节点弹出如果不为空则把右树赋值给cur继续遍历。如图当cur为9时右树不为空所以把8赋值cur此时8的右树为空所以输出8并弹出。下一轮循环中top依旧是9这样就陷入了死循环。应该记录右树是否被遍历过输出的判断条件是右树为空或者右树被遍历过。定义引用prev当8输出的时候把8赋值给prev这样下一轮循环中先判断prev是9的右树再输出9.voidpostOrder(TreeNoderoot){TreeNodecurroot;TreeNodeprevnull;StackTreeNodestacknewStack();while(cur!null||!stack.isEmpty()){while(cur!null){stack.push(cur);curcur.left;}TreeNodetopstack.peek();if(top.rightnull||prevtop.right){System.out.println(top.val);stack.pop();prevtop;}else{curtop.right;}}}
