学做网站论坛vip码,产品单页营销型网站模板,如何免费搭建网站源码,做网站开发的有哪些公司故事的开头#xff0c;我们先来三道不是oj的开胃菜#xff0c;练练手感#xff0c;后面9道都是OJ题。 目录
第一题
第二题
第三题
第四题
第五题
第六题
第七题
第八题
第九题
第十题
第十一题 第一题
二叉树前序非递归遍历实现 。 首先我们需要一个栈来存放二… 故事的开头我们先来三道不是oj的开胃菜练练手感后面9道都是OJ题。 目录
第一题
第二题
第三题
第四题
第五题
第六题
第七题
第八题
第九题
第十题
第十一题 第一题
二叉树前序非递归遍历实现 。 首先我们需要一个栈来存放二叉树里面的元素定义一个Tree Node类型的cur来指向要入栈的元素然后一直往栈里放root.left边放边打印全部放完就出栈。最后让cur指向栈顶元素也就是回退到不为空的节点再遍历right。stack.isEmpty()就是栈里面不为空就不用再写一遍while的打印循环了。 public void preOrderNot(TreeNode root) {StackTreeNode stack new Stack();if (root null) {return;}TreeNode cur root;while (cur ! null || !stack.isEmpty()) {while (cur ! null) {stack.push(cur);System.out.print(cur.val );cur cur.left;}TreeNode top stack.pop();cur top.right;}}
第二题
二叉树中序非递归遍历实现。 这也是同上面那一道题一样但是要注意的就是要先遍历完全部的left再打印而前序遍历是边遍历边打印。 public void inOrderNot(TreeNode root) {StackTreeNode stack new Stack();if (root null) return;TreeNode cur root;while (cur ! null || !stack.isEmpty()) {while (cur ! null) {stack.push(cur);cur cur.left;}TreeNode top stack.pop();System.out.print(top.val );cur top.right;}}
第三题 二叉树后序非递归遍历实现。 这道题稍微会比上面两道复杂一点但是大致思路也是一样的。如果完全按照上面两道题的思路就会陷入死循环。这里遇到空栈顶top不能直接pop需要peek看一下 因为一删就没有了找不到了后序遍历还没有打印这个节点得左右都打印完才能打印。所以需要看看right有没有元素。跟着代码就会死循环所以需要定义一个prev表示如果打印过了就不再循环退回上一个元素就不会死循环了。 public void postOrderNot(TreeNode root) {StackTreeNode stack new Stack();if (root null) {return;}TreeNode cur root;TreeNode prevnull;while (cur ! null || !stack.isEmpty()) {while (cur ! null) {stack.push(cur);cur cur.left;}TreeNode top stack.peek();//第二个条件说明被打印过了直接弹出他的父亲并打印if (top.right null||prevtop.right) {stack.pop();System.out.print(top.val );prevtop;} else {cur top.right;}}}
第四题
检查两颗树是否相同。 OJ链接 这道题非常简单从结构上开始考虑如果两个为空为true一个为空一个不为空结构长得都不一样所以false两个都不为空这时候才开始判断他们的值一不一样不一样false一样的话继续递归。 public boolean isSameTree(TreeNode p, TreeNode q) {// 两个为空if (p null q null) {return true;}//一个为空一个不为空if (p null q ! null) {return false;}if (p ! null q null) {return false;}//两个都不为空开始比较if (p.val ! q.val) {return false;}return isSameTree(p.left, q.left) isSameTree(p.right, q.right);}
第五题 另一颗树的子树。OJ链接 也是通过结构判断要判断的树为空直接false从最初的根开始就一样了 true左子树和子树一样true右子树一样也是true不然就是false。 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;}
第六题 翻转二叉树。OJ链接 树为空不能翻转返回null 。定义一个tmp来作为中间媒介交换左和右的元素由于父亲被带过去了所以孩子也会一整个被搬过去不用担心递归时子类的左右树不匹配。然后再把左子树和右子树都进行递归最后返回根节点。 public TreeNode invertTree(TreeNode root) {if(rootnull){return null;}TreeNode tmproot.left;root.leftroot.right;root.righttmp;invertTree(root.left);invertTree(root.right);return root;}
第七题 判断一颗二叉树是否是平衡二叉树。OJ链接 什么是平衡二叉树就是左子树和右子树高度差必须小于等于1。左子树如果树为空平衡true定义左高度和右高度用getHeight方法获取左右树的高度然后用绝对值方法abs来求高度差只要左子树和右子树高度差小于1并且左子树自己平衡右子树也平衡才true。 public boolean isBalanced(TreeNode root) {if(rootnull){return true;}int leftHgetHeight(root.left);int rightHgetHeight(root.right);return Math.abs(leftH-rightH)1isBalanced(root.left)isBalanced(root.right);}// 获取二叉树的高度public int getHeight(TreeNode root) {if(rootnull){return 0;}int leftHgetHeight(root.left);int rightHgetHeight(root.right);return Math.max(leftH,rightH)1;}
第八题
对称二叉树。 OJ链接 如果rootnull则是true书写一个检测子树对不对称的方法然后判断结构如果左子树为空右子树不为空或者右子树为空左子树不为空则结构不同false如果两个都为空则返回true如果两个都不为空则判断他们的值不一样就false一样的话就继续递归。 public boolean isSymmetric(TreeNode root) {if (root null) {return true;}return isSymmetricchild(root.left, root.right);}public boolean isSymmetricchild(TreeNode leftTree, TreeNode rightTree) {if (leftTree ! null rightTree null || leftTree null rightTree ! null) {return false;}if (leftTree null rightTree null) {return true;}if (leftTree.val ! rightTree.val) {return false;}return isSymmetricchild(leftTree.left, rightTree.right) isSymmetricchild(leftTree.right, rightTree.left);}
第九题 二叉树的构建及遍历。OJ链接 利用i遍历一个字符串charAt获取每个元素如果不为“#”则直接new TreeNodecharAti进去接到root后面是的话就i问题来了new了不就重新创建TreeNode了吗不会把之前的替换掉吗不会因为需要在后面的代码写上root.leftheroot.right递归下去new出来的root直接接到left和right上面了。 class TreeNode {public char val;public TreeNode left;public TreeNode right;public TreeNode(char val) {this.val val;}}public class Main {public static int i 0;public static TreeNode creatTree(String str) {TreeNode root null;if (str.charAt(i) ! #) {root new TreeNode(str.charAt(i));i;root.left creatTree(str);root.right creatTree(str);} else {i;}return root;}public static void inOrder(TreeNode root) {if (root null) {return;}inOrder(root.left);System.out.print(root.val );inOrder(root.right);}public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseString str in.nextLine();TreeNode root creatTree(str);inOrder(root);}}}
第十题 二叉树的分层遍历 。OJ链接 利用队列在装这些元素如果rootnull直接返回。不为空则入队一个root队列不为空的话把这个打印出来出队如果这个root左右子树不为空入队然后进行循环直到一整颗树被打印完。为什么用队列而不用栈呢如果用栈就从 右往左打印了显然不符合层序遍历的规律。 public void levelOrder(TreeNode root){QueueTreeNode queuenew LinkedList();if(rootnull){return;}queue.offer(root);while(!queue.isEmpty()){TreeNode curqueue.poll();System.out.print(cur.val );if(cur.left!null){queue.offer(cur.left);}if(cur.right!null){queue.offer(cur.right);}}System.out.println();}第十一题 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先 。OJ链接 也是利用结构判断如果rootnull返回null如果p和q任意有个人在root直接返回root如果没有继续递归看看左右子树如果左右子树都找得到p或q那么说明左右子树各有一个它的祖先必然是root如果都在左子树找到一个就返回都在右子树找到一个就返回。 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(rootnull){return null;}if(rootp||rootq){return root;}TreeNode leftTreelowestCommonAncestor(root.left,p,q);TreeNode rightTreelowestCommonAncestor(root.right,p,q);//左子树和右子树各一个if(leftTree!nullrightTree!null){return root;}//都在左子树,找到一个就返回else if(leftTree!null){return leftTree;}//都在右子树找到一个就返回else{return rightTree;}}
