【LeetCode二叉树OJ实战】刷完这几道经典题，面试不再怕！（Java版）

第一关基础遍历篇青铜----3道遍历是二叉树最基础的操作递归写法很简单但面试官最爱问的是非递归怎么写。其实就是用栈模拟递归搞懂入栈、出栈、打印的时机就行。通关目标手写前序、中序、后序的递归与非递归版本。1.1二叉树的前序遍历oj连接二叉树的前序遍历题目描述给你二叉树的根节点root返回它节点值的前序遍历。思路分析我们用非递归思想来考虑前序遍历的遍历顺序为根左右看题目要求返回的是数组的形式借助栈来实现public void preOrderNor(TreeNode root){ if(rootnull) return; StackTreeNode stacknew Stack(); TreeNode curroot; while(cur!null|| !stack.isEmpty()){ while(cur!null){ stack.push(cur); System.out.println(cur.val); curcur.left; } TreeNode topstack.pop(); curtop.right; } }1.2二叉树的中序遍历oj连接二叉树的中序遍历题目描述给定一个二叉树的根节点root返回它的中序遍历。思路分析中序遍历与前序遍历差不多都是借助栈来实现public void inOrderNor(TreeNode root){ if(rootnull) return; StackTreeNode stacknew Stack(); TreeNode curroot; while(cur!null||!stack.isEmpty()){ while(cur!null){ stack.push(cur); curcur.left; } TreeNode topstack.pop(); System.out.println(top.val); curtop.right; } }1.3二叉树的后序遍历oj连接二叉树的后序遍历题目描述给你一棵二叉树的根节点root返回其节点值的后序遍历。思路分析后序遍历稍微复杂些他虽然也是借助栈来实现但按照前序中序的套路会出现死循环现象所以我们新增一个变量prev来标记右孩子是否被打印过public void postOrderNor(TreeNode root){ if(rootnull) return; TreeNode curroot; TreeNode prevnull; StackTreeNode stacknew Stack(); while(cur!null||!stack.isEmpty()){ while(cur!null){ stack.push(cur); curcur.left; } TreeNode topstack.peek(); if(top.rightnull||top.rightprev){ System.out.println(top.val ); stack.pop(); prevtop; }else{ curtop.right; } } }第二关树的判定篇白银----4道判断两棵树是否相同、是否对称、是否平衡、或者翻转一下——这类题的共同点就是同时递归比较两个节点。核心就三步都空返回true、一个空返回false、值不等返回false剩下交给递归。通关目标熟练运用递归模板解决各类树的形态判定问题。2.1检查两棵树是否相同oj连接两棵树是否相同题目描述给你两棵二叉树的根节点p和q编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同并且节点具有相同的值则认为它们是相同的。思路分析根据题目要求我们需要判断两个点1.结构是否相同 2.节点的值是否相同。可以用递归的思想来判断两棵树是否相同先考虑结点是否为空的情况也就是结构是否相同当p为空q不为空或者q为空p不为空在这种情况下结构不同可以直接给出false接下来考虑节点值是否相同如果函数没有执行上述语句说明p和q要么都为空直接输出true要么都不为空在这个情况下判断val值一样输出true。后序的都可以交给递归来做这样依次判断即可public boolean isSameTree(TreeNode p, TreeNode q) { //先判断结构是否相同最干脆的判断方式 if(p!nullqnull||pnullq!null) return false; //如果没有执行上述if语句说明都为空或者都不为空 if(pnullqnull) return true; //都不为空判断值 if(p.val!q.val){ return false; } return isSameTree(p.left,q.left)isSameTree(p.right,q.right); }2.2对称二叉树oj连接对称二叉树题目描述给你一个二叉树的根节点root 检查它是否轴对称思路分析我们已经有上一道题判断两棵二叉树是否相同的经验这道题也如出一辙。判断二叉树是否轴对称就是判断根节点的左孩子和右孩子的结构是否相同节点值是否对称这个是区别于上一道不同的一点只需要做稍微改动判断p.right与q.left和p.left与q.right因此很容易想到延续上一种的思路注意不要忘记判断根节点为空的情况public boolean isSymmetric(TreeNode root) { if(rootnull) return true; return isSameTree(root.left,root.right); } public boolean isSameTree(TreeNode p, TreeNode q) { //先判断结构是否相同最干脆的判断方式 if(p!nullqnull||pnullq!null) return false; //如果没有执行上述if语句说明都为空或者都不为空 if(pnullqnull) return true; //都不为空判断值 if(p.val!q.val){ return false; } return isSameTree(p.right,q.left)isSameTree(p.left,q.right); }2.3判断平衡二叉树oj连接平衡二叉树题目描述思路分析看完题目中平衡二叉树的定义为了方便填写可以单独写一个求高度的方法。二叉树求高度在上一篇博客提到只需要满足高度差不超过1即可解答。public boolean isBalanced(TreeNode root) { if(rootnull) return true; int leftHeightheight(root.left); int rightHeightheight(root.right); return Math.abs(leftHeight-rightHeight)2isBalanced(root.left)isBalanced(root.right); } //定义求高函数 public int height(TreeNode root){ if(rootnull) return 0; int leftHeightheight(root.left); int rightHeightheight(root.right); return Math.max(leftHeight,rightHeight)1; }2.4翻转二叉树oj连接翻转二叉树题目描述给你一棵二叉树的根节点root翻转这棵二叉树并返回其根节点思路分析这道题往简单了想无非就是把结点的左右孩子换一下可以借助递归来做public TreeNode invertTree(TreeNode root) { if(rootnull) return null; TreeNode temproot.left; root.leftroot.right; root.righttemp; invertTree(root.left); invertTree(root.right); return root; }第三关构造与转换篇黄金----3道前两关是读树这一关是造树。给你前序中序或中序后序的遍历结果还原出原来的二叉树。核心思路就三句话前序/后序找根节点中序分左右子树递归构建。两道构造题代码几乎一样学会一道另一道顺手就写了。通关目标掌握根据遍历序列重建二叉树的核心套路。3.1前序中序构造二叉树oj连接前序和中序构造二叉树题目描述给定两个整数数组preorder和inorder其中preorder是二叉树的先序遍历inorder是同一棵树的中序遍历请构造二叉树并返回其根节点。思路分析依照上图的流程我们需要在中序遍历出的结果里一遍遍找到根节点FindVal函数实现所以定义几个变量方便操作注意postIndex单独拎出来是因为它像一个全局指针所有递归层必须共享同一个进度。用成员变量是最直观、最简单的实现方式。public int preIndex; public TreeNode buildTree(int[] preorder, int[] inorder) { return buildTreeChild(preorder, inorder, 0, inorder.length - 1); } public TreeNode buildTreeChild(int[] preorder, int[] inorder, int inbegin, int inend) { //给一个递归出口 if (inbegin inend) return null; //先创建根 TreeNode root new TreeNode(preorder[preIndex]); int rootIndex FindVal(inorder, inbegin, inend, preorder[preIndex]); preIndex; //创建左子树 root.left buildTreeChild(preorder, inorder, inbegin, rootIndex - 1); //创建右子树 root.right buildTreeChild(preorder, inorder, rootIndex 1, inend); return root; } public int FindVal(int[] inorder, int inbegin, int inend, int val) { for (int i inbegin; i inend; i) { if (inorder[i] val) { return i; } } return -1; }3.2中序后序构造二叉树oj连接中序与后序遍历二叉树题目描述给定两个整数数组inorder和postorder其中inorder是二叉树的中序遍历postorder是同一棵树的后序遍历请你构造并返回这颗二叉树。思路分析这道与上一题很相似只需稍作改动即可public int postIndex; public TreeNode buildTree(int[] inorder, int[] postorder) { postIndexpostorder.length-1; return buildTreeChild(inorder,postorder,0,inorder.length-1); } public TreeNode buildTreeChild(int[] inorder, int[] postorder,int inbegin,int inend) { //先规定递归出口 if(inbegininend) return null; //创建根 TreeNode rootnew TreeNode(postorder[postIndex]); int rootIndexFindVal(inorder,inbegin,inend,postorder[postIndex]); postIndex--; //在创建右子树 root.rightbuildTreeChild(inorder,postorder,rootIndex1,inend); //最后创建左子树 root.leftbuildTreeChild(inorder,postorder,inbegin,rootIndex-1); return root; } public int FindVal(int[] inorder,int inbegin,int inend,int val){ for(int iinbegin;iinend;i){ if(inorder[i]val){ return i; } } return -1; }3.3二叉树创建字符串oj连接二叉树创建字符串题目描述给你二叉树的根节点root请你采用前序遍历的方式将二叉树转化为一个由括号和整数组成的字符串返回构造出的字符串。空节点使用一对空括号对()表示转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。思路分析只有一种情况必须加空括号()——左子树为空但右子树不为空。因为不加的话解析器会把右子树的括号误认为是左子树的导致结构混乱。注意用stringBuilder是因为String 是不可变的而 StringBuilder 是可变的。在递归拼接字符串时StringBuilder 能大幅提升性能并且更方便地在不同递归层之间“共享”同一个拼接结果public String tree2str(TreeNode root) { if(rootnull) return null; StringBuilder stringBuildernew StringBuilder(); tree2strChild(root,stringBuilder); return stringBuilder.toString(); } public void tree2strChild(TreeNode root,StringBuilder stringBuilder) { if(rootnull) return ; //先把根节点写进去 stringBuilder.append(root.val); //左子树情况 if(root.left!null){ stringBuilder.append((); tree2strChild(root.left,stringBuilder); stringBuilder.append()); }else{ if(root.rightnull){ return; }else{ stringBuilder.append(()); } } //右子树情况 if(root.right!null){ stringBuilder.append((); tree2strChild(root.right,stringBuilder); stringBuilder.append()); }else{ return; } }第四关综合应用题王者----2道前面学过的递归、栈、队列、分治、回溯在这一关全部派上用场。另一棵树的子树遍历大树每到一个节点就判断一下以它为根的子树是否和目标树相同其实就是前序遍历 判断相同树。二叉树的构建及遍历根据输入字符串用特殊符号表示空节点递归建树考察对序列化和反序列化的理解。通关目标综合运用前四关的技能做完这两道题二叉树基本毕业。4.1另一棵树的子树oj连接另一棵树的子树题目描述给你两棵二叉树root和subRoot。检验root中是否包含和subRoot具有相同结构和节点值的子树。如果存在返回true否则返回false。二叉树tree的一棵子树包括tree的某个节点和这个节点的所有后代节点。tree也可以看做它自身的一棵子树。思路分析判断一棵树是否为另一棵树的子树无非就是判断值和结构是否相同又回到了第二关----判断两棵树是否相同与思路类似依次判断subRoot与这棵二叉树的左子树右子树是否相同即可public boolean isSubtree(TreeNode root, TreeNode subRoot) { if(rootnull) return false; if(isSameTree(root,subRoot)) return true; if(isSubtree(root.left,subRoot)) return true; if(isSubtree(root.right,subRoot)) return true; return false; } public boolean isSameTree(TreeNode p, TreeNode q) { //先判断结构是否相同最干脆的判断方式 if(p!nullqnull||pnullq!null) return false; //如果没有执行上述if语句说明都为空或者都不为空 if(pnullqnull) return true; //都不为空判断值 if(p.val!q.val){ return false; } return isSameTree(p.left,q.left)isSameTree(p.right,q.right); }4.2二叉树的构建及遍历oj连接二叉树的构建及遍历题目描述编一个程序读入用户输入的一串先序遍历字符串根据此字符串建立一个二叉树以指针方式存储。 例如如下的先序遍历字符串 ABC##DE#G##F### 其中“#”表示的是空格空格字符代表空树。建立起此二叉树以后再对二叉树进行中序遍历输出遍历结果。思路分析用代码的逻辑遇到非#就创建节点并递归遇到#就跳过返回空。public class Main { public static void main(String[] args) { Scanner in new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 while (in.hasNextLine()) { // 注意 while 处理多个 case String strin.nextLine(); TreeNode rootCreateTree(str); inorder(root); } } public static int i0; //创建树 public static TreeNode CreateTree(String str){ TreeNode rootnull; if(str.charAt(i)!#){ rootnew TreeNode(str.charAt(i)); i; root.leftCreateTree(str); root.rightCreateTree(str); }else{ i; } return root; } //中序遍历 public static void inorder(TreeNode root){ if(rootnull) return; inorder(root.left); System.out.print(root.val ); inorder(root.right); } }