企业官网建设流程全解析

1. 二叉搜索树与双向链表（BM30）

二叉搜索树与双向链表

题目描述

解题思路

题目要求返回一个固定节点，而递归调用是多次的，所以要分成两个方法。

• ConvertChild（）：
  • 搜索二叉树的特点是：中序遍历得到的结果是有序的所以要采用中序遍历。
  • prev来记录前一个节点。prev必须是类变量，不可以是局部变量，因为递归调用会重复把prev置空。
  • 转换成双向链表，left和right就代表逻辑链表节点上的左右。当前节点的left置为prev，prev（不为空的情况下）的right置为root。prev置为root
  • 此时题目给的pRootOfTree是链表的中心，把head移到链表左端，并返回

代码示例

publicclassSolution{TreeNodeprev=null;publicTreeNodeConvert(TreeNodepRootOfTree){if(pRootOfTree==null)returnnull;ConvertChild(pRootOfTree);TreeNodehead=pRootOfTree;while(head.left!=null)head=head.left;returnhead;}publicvoidConvertChild(TreeNoderoot){if(root==null)return;ConvertChild(root.left);if(prev!=null)prev.right=root;root.left=prev;prev=root;ConvertChild(root.right);}}

2. 二叉树遍历（KY11）

二叉树遍历

题目描述

解题思路

• createTree（）:遍历字符串，因为函数要循环调用，字符串要依次遍历，所以下标i应该是类变量而非局部变量。
• 如果字符不是#，则创建新节点，i自增，接着创建左树和右树
• 如果字符是#，则i自增，不创建节点。此时root还是null，返回上一个函数。
• main函数：先调用createTree（），再中序遍历二叉树，输出字符
• 为了防止牛客网给出多组测试字符串造成i过大，i要手动置为0

代码示例

publicclassMain{publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);while(in.hasNext()){Stringstr=in.nextLine();TreeNodenode=createTree(str);inOrder(node);i=0;}}publicstaticinti=0;staticTreeNodecreateTree(Stringstr){TreeNoderoot=null;if(str.charAt(i)!='#'){root=newTreeNode(str.charAt(i));i++;root.left=createTree(str);root.right=createTree(str);}elsei++;returnroot;}staticvoidinOrder(TreeNoderoot){if(root==null)return;inOrder(root.left);System.out.print(root.val+" ");inOrder(root.right);}}

3. 二叉树的层序遍历（LC102）

二叉树的层序遍历

题目描述

解题思路

当队列不为空时，循环处理每一层：

• 先获取当前队列大小，即当前层的节点数量
• 创建一个临时列表存储当前层的节点值
• 循环取出当前层的所有节点（循环次数为当前层节点数）：
  • 取出队首节点，将其值加入临时列表
  • 如果该节点有左子节点，将左子节点入队
  • 如果该节点有右子节点，将右子节点入队
• 当前层处理完毕后，将临时列表加入结果列表

代码示例

publicList<List<Integer>>levelOrder(TreeNoderoot){List<List<Integer>>ret=newArrayList<>();if(root==null)returnret;Queue<TreeNode>queue=newLinkedList<>();queue.offer(root);while(!queue.isEmpty()){intsize=queue.size();List<Integer>list=newArrayList<>();while(size!=0){TreeNodecur=queue.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)

二叉树的公共祖先

题目描述

解题思路

思路一：

可以分成三种情况：

1. 根节点root就是p或q 直接返回root
2. p和q分别在左树和右树
3. p和q都在左树或都在右树

分别定义 leftTree ，rightTree 在子树中遍历，如果两个都不是空，证明p，q在左右两侧，那么root就是最小公共祖先；如果其中一个为空，证明p，q在同一侧，返回已找到的公共祖先。

思路二：

利用栈存储从根节点到p和q的路径，找公共节点

• getPath（）：先让root入栈，如果node是root，返回true；接着在左右子树寻找路径，如果左右子树中都没有，说明当前节点不是到达node的经过的节点，出栈。

代码示例

• 思路一：

publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){if(root==null)returnnull;if(p==root||q==root)returnroot;TreeNodeleftTree=lowestCommonAncestor(root.left,p,q);TreeNoderightTree=lowestCommonAncestor(root.right,p,q);if(leftTree!=null&&rightTree!=null)returnroot;elseif(leftTree!=null)returnleftTree;elsereturnrightTree;}

• 思路二：

booleangetPath(TreeNodenode,TreeNoderoot,Stack<TreeNode>stack){if(root==null)returnfalse;stack.push(root);if(root==node)returntrue;booleanret=getPath(node,root.left,stack);if(ret)returntrue;ret=getPath(node,root.right,stack);if(ret)returntrue;stack.pop();returnfalse;}publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){if(root==null)returnnull;Stack<TreeNode>s1=newStack<>();Stack<TreeNode>s2=newStack<>();getPath(p,root,s1);getPath(q,root,s2);intsize1=s1.size();intsize2=s2.size();if(size1>size2){intsize=size1-size2;while(size!=0){s1.pop();size--;}}else{intsize=size2-size1;while(size!=0){s2.pop();size--;}}while(!s1.isEmpty()){TreeNodetmp1=s1.pop();TreeNodetmp2=s2.pop();if(tmp1==tmp2){returntmp1;}}returnnull;}

5. 从前序和中序遍历序列构建二叉树（LC105）

从前序和中序遍历序列构建二叉树

题目描述

解题思路

为了便于递归下标参数的传递，另写一个函数。

前序遍历确定根节点，所以先创建根节点，在中序数组中找到根节点值的下标，下一次传参时创建左树的右边界就是preIndex-1；创建右树的左边界就是preIndex+1。

代码示例

intpreIndex;publicTreeNodebuildTree(int[]preorder,int[]inorder){returnbuildTreeChile(preorder,inorder,0,inorder.length-1);}publicTreeNodebuildTreeChile(int[]preorder,int[]inorder,intinBegin,intinEnd){if(inBegin>inEnd)returnnull;TreeNoderoot=newTreeNode(preorder[preIndex]);introotIndex=getIndex(preorder[preIndex],inorder,inBegin,inEnd);preIndex++;root.left=buildTreeChile(preorder,inorder,inBegin,rootIndex-1);root.right=buildTreeChile(preorder,inorder,rootIndex+1,inEnd);returnroot;}intgetIndex(intval,int[]inorder,intinBegin,intinEnd){for(inti=inBegin;i<=inEnd;i++){if(inorder[i]==val)returni;}return-1;}

6. 从中序和后序遍历序列构建二叉树（LC106）

从中序和后序遍历序列构建二叉树

题目描述

解题思路

与上一题的解法类似。需要注意的是：后序遍历的顺序是左 右 根，所以要在后序数组中从后往前遍历，先确定根节点，再创建右树，再创建左子树。

代码示例

intpostIndex;publicTreeNodebuildTree(int[]inorder,int[]postorder){postIndex=postorder.length-1;returnbuildTreeChild(inorder,postorder,0,inorder.length-1);}publicTreeNodebuildTreeChild(int[]inorder,int[]postorder,intinBegin,intinEnd){if(inBegin>inEnd)returnnull;TreeNoderoot=newTreeNode(postorder[postIndex]);introotIndex=getIndex(postorder[postIndex],inorder,inBegin,inEnd);postIndex--;root.right=buildTreeChild(inorder,postorder,rootIndex+1,inEnd);root.left=buildTreeChild(inorder,postorder,inBegin,rootIndex-1);returnroot;}intgetIndex(intval,int[]inorder,intinBegin,intinEnd){for(inti=inBegin;i<=inEnd;i++){if(inorder[i]==val)returni;}return-1;}

7. 根据二叉树创建字符串（LC606）

根据二叉树创建字符串

题目描述

解题思路

为了方便函数递归传参，新写一个函数。

1. 先添加root的值，再判断左树，如果左树不为空，添加左括号，递归调用添加左数的值，添加右括号，
2. 如果左树为空，再判断此时右树，右树如果也为空，就可以直接返回，如果右树不为空，那么左树的括号不能省略。
3. 再单独判断右树，如果右树不为空，与左树类似，先添加左括号，再递归调用，再添加右括号

代码示例

publicStringtree2str(TreeNoderoot){StringBuilderret=newStringBuilder();tree2strChild(root,ret);returnret.toString();}voidtree2strChild(TreeNoderoot,StringBuilders){if(root==null)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){TreeNodecur=root;Stack<TreeNode>stack=newStack<>();while(cur!=null||!stack.isEmpty()){while(cur!=null){stack.push(cur);System.out.println(cur.val+" ");cur=cur.left;}TreeNodetop=stack.pop();cur=top.right;}}

9. 非递归法中序遍历（LC94）

非递归法中序遍历
与前序遍历类似，区别在于中序遍历先访问左树，所以要在内层循环结束（也就是到左子树尽头）再弹出并访问

voidinOrder(TreeNoderoot){TreeNodecur=root;Stack<TreeNode>stack=newStack<>();while(cur!=null||!stack.isEmpty()){while(cur!=null){stack.push(cur);cur=cur.left;}TreeNodetop=stack.pop();System.out.println(top.val+" ");cur=top.right;}}

10. 非递归法后序遍历（LC145）

OJ 非递归法后序遍历

后序遍历要先保证右树遍历后再访问根，所以在输出根之前，先判断右树是否为空，如果为空，输出根节点并把根节点弹出；如果不为空则把右树赋值给cur继续遍历。

• 如图，当cur为9时，右树不为空，所以把8赋值cur，此时8的右树为空，所以输出8并弹出。
• 下一轮循环中top依旧是9，这样就陷入了死循环。
• 应该记录右树是否被遍历过，输出的判断条件是右树为空或者右树被遍历过。
• 定义引用prev，当8输出的时候把8赋值给prev，这样下一轮循环中先判断prev是9的右树，再输出9.
  

voidpostOrder(TreeNoderoot){TreeNodecur=root;TreeNodeprev=null;Stack<TreeNode>stack=newStack<>();while(cur!=null||!stack.isEmpty()){while(cur!=null){stack.push(cur);cur=cur.left;}TreeNodetop=stack.peek();if(top.right==null||prev==top.right){System.out.println(top.val);stack.pop();prev=top;}else{cur=top.right;}}}