科技网站设计案例,苏州市网站建设培训,陕西省住房和城乡建设厅官网查询,行业查询网站专栏#xff1a;Java数据结构秘籍 个人主页#xff1a;手握风云 目录
一、二叉树OJ练习题#xff08;续#xff09;
1.1. 二叉树的层序遍历
1.2. 二叉树的最近公共祖先
1.3. 从前序与中序遍历序列构造二叉树
1.4. 从中序与后序遍历序列构造二叉树
1.5. 根据二叉树创建… 专栏Java数据结构秘籍 个人主页手握风云 目录
一、二叉树OJ练习题续
1.1. 二叉树的层序遍历
1.2. 二叉树的最近公共祖先
1.3. 从前序与中序遍历序列构造二叉树
1.4. 从中序与后序遍历序列构造二叉树
1.5. 根据二叉树创建字符串
一、二叉树OJ练习题续
1.1. 二叉树的层序遍历 层序遍历就是从左到右依次访问每个节点。这里我们要借助队列来非递归方式的实现。我们先将根结点root放入队列再用cur引用来接收弹出的根结点最后再打印。当左右子树不为空时再一次将左子树和右子树放入队列中。然后先弹出左子树如果左子树的左右结点不为空再次放入。当队列为空时遍历过程结束。所以下面这棵二叉树的打印结果应为“4271369”。 import java.util.LinkedList;
import java.util.Queue;class TreeNode{public int val;public TreeNode left;public TreeNode right;public TreeNode() {}public TreeNode(int val) {this.val val;}public TreeNode(int val, TreeNode left, TreeNode right) {this.val val;this.left left;this.right import java.util.LinkedList;
import java.util.Queue;class TreeNode{public int val;public TreeNode left;public TreeNode right;public TreeNode() {}public TreeNode(int val) {this.val val;}public TreeNode(int val, TreeNode left, TreeNode right) {this.val val;this.left left;this.right right;}
}public class Solution {public void levelOrder(TreeNode root){QueueTreeNode queue new LinkedListTreeNode();queue.offer(root);while(! queue.isEmpty()){TreeNode cur queue.poll();System.out.print(cur.val );if(cur.left ! null){queue.offer(cur.left);}if(cur.right ! null){queue.offer(cur.right);}}}
} right;}
}public class Solution {public void levelOrder(TreeNode root){QueueTreeNode queue new LinkedListTreeNode();queue.offer(root);while(! queue.isEmpty()){TreeNode cur queue.poll();System.out.print(cur.val );if(cur.left ! null){queue.offer(cur.left);}if(cur.right ! null){queue.offer(cur.right);}}}
}
public class Test {public static void main(String[] args) {TreeNode root new TreeNode(4,new TreeNode(2),new TreeNode(7));root.left.left new TreeNode(1);root.left.right new TreeNode(3);root.right.left new TreeNode(6);root.right.right new TreeNode(9);Solution solution new Solution();solution.levelOrder(root);}
} 但题目当中给出的类型是嵌套ListListInteger同时根据输出的格式来创建一个二维数组第一层放入第一列中。我们依然可以借助上面的队列来实现。与上面的方法类似我们还需要再定义一个整型size变量来接受队列的长度根据队列的长度来选择弹出与进入的操作。 public ListListInteger levelOrder1(TreeNode root){ListListInteger ret new ArrayList();if(root null) return ret;QueueTreeNode queue1 new LinkedListTreeNode();queue1.offer(root);while(! queue1.isEmpty()){ListInteger curList new ArrayList();int size queue1.size();while(size ! 0){TreeNode cur queue1.poll();curList.add(cur.val);if(cur.left ! null){queue1.offer(cur.left);}if(cur.right ! null){queue1.offer(cur.right);}size--;}ret.add(curList);}return ret;}
import java.util.List;public class Test {public static void main(String[] args) {Solution solution new Solution();TreeNode root new TreeNode(4,new TreeNode(2),new TreeNode(7));root.left.left new TreeNode(1);root.left.right new TreeNode(3);root.right.left new TreeNode(6);root.right.right new TreeNode(9);solution.levelOrder(root);ListListInteger result solution.levelOrder1(root);System.out.println(result);}
}1.2. 二叉树的最近公共祖先 如果是上图中第三种情况那么我们就直接返回root。如果是第一种情况当root向下遍历时遇到p、q结点时直接返回到root如下图所示。 如果是第二种情况当root遍历到p节点时5结点返回p的地址同时我们也可以找到q结点并返回。但还是有一种极端情况q是孩子节点p的一个子结点。按照上面的思路直接就返回这个结点。所以这种极端情况可以总结为只要root遍历到p或者q中一个直接返回对应的结点。因为p、q都在同一棵子树上当root去遍历另一棵子树时会返回null所以最终结果是p与p或q在根节点上是类似的。 完整代码实现
class TreeNode{public int val;public TreeNode left;public TreeNode right;public TreeNode() {}public TreeNode(int val) {this.val val;}public TreeNode(int val, TreeNode left, TreeNode right) {this.val val;this.left left;this.right right;}
}public class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){if(root null){return root;}if(root p || root q){return root;}TreeNode leftT lowestCommonAncestor(root.left,p,q);TreeNode rightT lowestCommonAncestor(root.right,p,q);if(leftT ! null rightT ! null){//p、q分别在左右子树上return root;}else if(leftT ! null){return leftT;} else if (rightT ! null) {return rightT;}return null;}
}public class Test {public static void main(String[] args) {TreeNode root new TreeNode(3,new TreeNode(5),new TreeNode(1));root.left.left new TreeNode(6);root.left.right new TreeNode(2,new TreeNode(7),new TreeNode(4));root.right.left new TreeNode(0);root.right.right new TreeNode(8);TreeNode p root.left;TreeNode q root.right;Solution solution new Solution();TreeNode cur solution.lowestCommonAncestor(root,p,q);System.out.println(cur.val);}
}这道题还有另一种做法如果我们把二叉树里的每一个结点新增加一个前驱域用来存储父节点的地址那么这道题的思路就变成了一链表交点的形式来求最近的公共祖先结点。可是定义的TreeNode类里面的成员变量里面没有这个变量。此时可以利用两个栈来存储从root到p、q结点路径上的结点。 基本思路只要root不为空就把结点扔进栈当中。让长度较大的栈先弹出一定的元素使得两个栈长度相等。两个栈再同时弹出元素判断两个值是否相等相等则是最近的公共祖先结点。 而下面问题又来了我们该如何求路径上的结点只要root不等于p或者q就将该节点放进栈中并继续递归当root等于p或者q时就停止。如果在遍历过程中某一个结点既不等于p、q且左右都为空那么这个元素就会被弹出。 完整代码实现
import java.util.Stack;class TreeNode{public int val;public TreeNode left;public TreeNode right;public TreeNode() {}public TreeNode(int val) {this.val val;}public TreeNode(int val, TreeNode left, TreeNode right) {this.val val;this.left left;this.right right;}
}public class Solution {public boolean getPath(TreeNode root, TreeNode node, StackTreeNode stack){if(root null){return false;}stack.push(root);if(root node){return true;}boolean flag getPath(root.left,node,stack);if(flag){return true;}flag getPath(root.right,node,stack);if(flag){return true;}stack.pop();return false;}public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){if(root null){return null;}StackTreeNode stack1 new Stack();StackTreeNode stack2 new Stack();getPath(root,p,stack1);getPath(root,q,stack2);int len1 stack1.size();int len2 stack2.size();int len len1 - len2;if(len 0){len Math.abs(len);while(len ! 0){stack2.pop();len--;}}else{while(len ! 0){stack1.pop();len--;}}//保证两个栈的长度一样while (!stack1.isEmpty() !stack2.isEmpty()){if(stack1.peek() stack2.peek()){return stack1.pop();}else{stack1.pop();stack2.pop();}}return null;}
}
public class Test {public static void main(String[] args) {TreeNode root new TreeNode(3,new TreeNode(5),new TreeNode(1));root.left.left new TreeNode(6);root.left.right new TreeNode(2,new TreeNode(7),new TreeNode(4));root.right.left new TreeNode(0);root.right.right new TreeNode(8);TreeNode p root.left;TreeNode q root.right;Solution solution new Solution();TreeNode cur solution.lowestCommonAncestor(root,p,q);System.out.println(cur.val);}
}
1.3. 从前序与中序遍历序列构造二叉树 基本思路1.遍历前序遍历的数组遇到元素之后在中序遍历数组当中找到该数字2.该数字的左边就是左树右边就是右树。上述两步构成一个递归来构造子树。 我们以中序遍历的数组的第一个元素ibegin最后一个元素iend之间找到二叉树的根因为是前序遍历先有的左树再有的右树那么左边的区间就会是(9,x) (ibegin,iend)iend iroot-1相反我们去递归右树ibeginiroot1。也就是说递归根结点创建左树和右树时还需要知道ibegin和iend的范围。 我们还需要额外创建一个方法来接受ibegin和iend的参数。创建root利用buildTreeChild方法递归来创建根结点的左树和右树。可我们不知道中序遍历的数组中根结点的下标还需要一个方法来查找根结点的下标。
public class Solution {public TreeNode buildTree(int[] preorder, int[] inorder){return buildTreeChild(preorder,0,inorder,0, inorder.length-1);}public TreeNode buildTreeChild(int[] preorder, int prevIndex,int[] inorder, int inbegin, int inend){TreeNode root new TreeNode(preorder[prevIndex]);int rootIndex findIndex(inorder,inbegin,inend,preorder[prevIndex]);prevIndex;root.left buildTreeChild(preorder,prevIndex,inorder,inbegin,rootIndex-1);root.right buildTreeChild(preorder,prevIndex,inorder,rootIndex-1,inend);return root;}private int findIndex(int[] inorder,int inbegin,int inend,int key) {for(int i inbegin; i inend; i) {if(inorder[i] key) {return i;}}return -1;}
}但此时的代码还是有一点逻辑上的问题就是递归结束的条件是什么一棵二叉树总有一棵子树的左右子树都为空。但我们上面的代码没有null。所以要处理一下边界情况
if(inbegin inend){return null;
} 还存在另一个问题就是局部变量的定义。因为二叉树遍历完左树的时候最后给根返回0从0再去遍历右子树。所以我们把prevIndex定义为成员变量。 完整代码实现
class TreeNode{int val;TreeNode left;TreeNode right;public TreeNode() {}public TreeNode(int val) {this.val val;}public TreeNode(int val, TreeNode left, TreeNode right) {this.val val;this.left left;this.right right;}
}public class Solution {public int prevIndex;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[prevIndex]);int rootIndex findIndex(inorder,inbegin,inend,preorder[prevIndex]);prevIndex;root.left buildTreeChild(preorder,inorder,inbegin,rootIndex-1);root.right buildTreeChild(preorder,inorder,rootIndex1,inend);return root;}private int findIndex(int[] inorder,int inbegin,int inend,int key) {for(int i inbegin; i inend; i) {if(inorder[i] key) {return i;}}return -1;}
}
public class Test {public static void PrintTreeNode(TreeNode root){if(root null){return;}System.out.print(root.val );PrintTreeNode(root.left);PrintTreeNode(root.right);}public static void main(String[] args) {Solution soluion new Solution();int[] preOrder new int[]{3,9,20,15,7};int[] inOrder new int[]{9,3,15,20,7};TreeNode root soluion.buildTree(preOrder,inOrder);PrintTreeNode(root);}
}
1.4. 从中序与后序遍历序列构造二叉树 与上面一题的思路一样但后序遍历的顺序是“左子树、右子树、根”那根结点从后面开始找。并且在创建树的过程中要先创建右树再创建左树。
class TreeNode{int val;TreeNode left;TreeNode right;public TreeNode() {}public TreeNode(int val) {this.val val;}public TreeNode(int val, TreeNode left, TreeNode right) {this.val val;this.left left;this.right right;}
}public class Solution {public int postIndex 0;public TreeNode buildTree(int[] inorder, int[] postorder){postIndex postorder.length-1;return buildTreeChild(postorder,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[postIndex]);int rootIndex findIndex(inorder,inbegin,inend,preorder[postIndex]);postIndex--;root.right buildTreeChild(preorder,inorder,rootIndex1,inend);root.left buildTreeChild(preorder,inorder,inbegin,rootIndex-1);return root;}private int findIndex(int[] inorder,int inbegin,int inend,int key) {for(int i inbegin; i inend; i) {if(inorder[i] key) {return i;}}return -1;}
}
public class Test {public static void PrintTreeNode(TreeNode root){if(root null){return;}PrintTreeNode(root.left);PrintTreeNode(root.right);System.out.print(root.val );}public static void main(String[] args) {Solution solution new Solution();int[] Inorder new int[]{9,3,15,20,7};int[] Postorder new int[]{9,15,7,20,3};TreeNode root solution.buildTree(Inorder,Postorder);PrintTreeNode(root);}
} 1.5. 根据二叉树创建字符串 通过上图分析当1的左子树不为空就用一个(2的左子树也不为空也使用一个(4再往下递归返回null直接)闭合2的右子树为null返回)1的右子树不为空返回(3递归返回null直接)闭合。 所以我们可以总结下来规律当子树不为空时直接加左括号当root的左树为空且右树也为空直接加右括号闭合当root的左树不为空右树为空也加右括号闭合。 public void tree2strChild(TreeNode root,StringBuilder stringBuilder){if(root null){return;}stringBuilder.append(root.val);//判断根的左子树if(root.left ! null){stringBuilder.append(();tree2strChild(root.left,stringBuilder);//递归左树stringBuilder.append());//左树走完右括号闭合}else {if(root.right null){return;//因为4结点走完返回2结点这里本身就会加一个)}else {}}//判断根的右子树if(root.right ! null){stringBuilder.append(();tree2strChild(root.right,stringBuilder);stringBuilder.append());}else {}} 但也存在另一种情况如果子树的左边为空右边不为空就直接加一对小括号再去递归右树把4再加进去。再继续往下走如果root.right为空正好符合上面2结点的情况2的左边走完右边为空直接return加右括号。所以只要左树为空右树不为空就不做任何处理。 完整代码实现
class TreeNode{public int val;public TreeNode left;public TreeNode right;public TreeNode() {}public TreeNode(int val) {this.val val;}public TreeNode(int val, TreeNode left, TreeNode right) {this.val val;this.left left;this.right right;}
}public class Solution {public String tree2str(TreeNode root){StringBuilder stringBuilder new StringBuilder();tree2strChild(root,stringBuilder);return stringBuilder.toString();}public void tree2strChild(TreeNode root,StringBuilder stringBuilder){if(root null){return;}stringBuilder.append(root.val);//判断根的左子树if(root.left ! null){stringBuilder.append(();tree2strChild(root.left,stringBuilder);//递归左树stringBuilder.append());//左树走完右括号闭合}else {if(root.right null){return;//因为4结点走完返回2结点这里本身就会加一个)}else {stringBuilder.append(());}}//判断根的右子树if(root.right ! null){stringBuilder.append(();tree2strChild(root.right,stringBuilder);stringBuilder.append());}else {return;}}
}
public class Test {public static void main(String[] args) {Solution solution new Solution();TreeNode root1 new TreeNode(1,new TreeNode(2),new TreeNode(3));root1.left.left new TreeNode(4);TreeNode root2 new TreeNode(1,new TreeNode(2),new TreeNode(3));root2.left.right new TreeNode(4);System.out.println(solution.tree2str(root1));System.out.println(solution.tree2str(root2));}
}
