简单的网站管理系统,网站搭建教学,婚礼策划网站模板,兰州网站seo收费标准文章目录 判断是否是完全二叉树找出p和q的最近的公共祖先非递归实现前序遍历非递归实现中序遍历非递归实现后序遍历 判断是否是完全二叉树 boolean isCompleteTree(TreeNode root){if (root null){return true;}//创建队列QueueTreeNode queue new LinkedList null){return true;}//创建队列QueueTreeNode queue new LinkedList();//把根放进队列里queue.offer(root);while (!queue.isEmpty()){//把出队列的放进cur里TreeNode cur queue.poll();//当cur不等于空时把cur的左子树和右子树放进队列if (cur ! null){queue.offer(cur.left);queue.offer(cur.right);}else{//如果cur放进了null说明要跳出队列进入判断环节break;}}while(!queue.isEmpty()){TreeNode tmp queue.peek();//瞄一眼队列的数if (tmp null){queue.poll();}else{//遇到不为空的说明不是完全二叉树return false;}}//来到这里说明tmp全部是空的,是完全二叉树return true;}找出p和q的最近的公共祖先
1.root节点是p或q其中的一个那么root就是最近的公共祖先 2.p和q分别在root的两侧那么root是最近的公共祖先 3.p和q在root的同一侧 原理root还是在遍历这棵树遇到p或q就返回。
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root null) return null;if (root p || root q) {return root;}TreeNode leftTree lowestCommonAncestor(root.left, p, q);TreeNode rightTree lowestCommonAncestor(root.left, p, q);if (leftTree ! null rightTree ! null) {return root;} else if (leftTree ! null) {return leftTree;} else {return rightTree;}}还有第二种方法 大概意思就是找p那条路径和q那条路径出现的节点然后放进两个栈里保证两个栈的数相同多的去掉然后栈中相同的元素就是他们最近的公共祖先。
public class BinaryTree {static class TreeNode{public char val;public TreeNode left;public TreeNode right;public TreeNode(char val) {this.val val;}}public TreeNode creatTree(){TreeNode A new TreeNode(A);TreeNode B new TreeNode(B);TreeNode C new TreeNode(C);TreeNode D new TreeNode(D);TreeNode E new TreeNode(E);TreeNode F new TreeNode(F);TreeNode G new TreeNode(G);TreeNode H new TreeNode(H);A.left B;A.right C;B.left D;B.right E;C.left F;C.right G;E.right H;return A;}public TreeNode lowestCommonAncestor2(TreeNode root,TreeNode p,TreeNode q){if(root null) return null;//创建两个栈StackTreeNode stackP new Stack();StackTreeNode stackQ new Stack();//两条路径getPath(root,p,stackP);getPath(root,q,stackQ);//大小int sizeP stackP.size();int sizeQ stackP.size();if (sizeP sizeQ){int size sizeP - sizeQ;while (size ! 0){stackP.pop();size--;}}else {int size sizeQ - sizeP;while (size ! 0){stackQ.pop();size--;}}//两个栈元素一样多while(!stackP.isEmpty() !stackQ.isEmpty()){if (stackP.peek() stackQ.peek()){return stackP.peek() ;}else{stackP.pop();stackQ.pop();}}return null;}private boolean getPath(TreeNode root, TreeNode node, StackTreeNode stack){if (root null || node null){return false;}stack.push(root);if (root node){return true;}boolean flg1 getPath(root.left, node, stack);if(flg1){return true;}boolean flg2 getPath(root.right, node, stack);if(flg2){return true;}stack.pop();return false;}
}非递归实现前序遍历 //递归实现前序遍历void preOrder(TreeNode root){//根左右if(root null){return;}System.out.print(root.val );preOrder(root.left);preOrder(root.right);}
//非递归实现前序遍历void preOrderNor(TreeNode root) {if (root null) {return;}StackTreeNode stack new Stack();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;//1.为空返回不为空创建栈让curroot;//当cur!null时把cur放进栈里并打印cur.val再让curroot.left。//当curnull时让top栈顶元素,然后让curtop.right}}非递归实现中序遍历 //中序遍历void inOrder(TreeNode root){//左根右if(root null){return;}inOrder(root.left);System.out.print(root.val );inOrder(root.right);}//非递归中序遍历void inorderNor(TreeNode root){if (root null){return;}StackTreeNode stack new Stack();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;}//不为空创建栈让curroot,把cur放进栈里然后遍历cur的左边。//直到cur遇到空说明cur的左边遍历完了//让top栈顶元素并打印top的值让curtop.right。}非递归实现后序遍历 //后序遍历void postOrder(TreeNode root){//左右根if(root null){return;}postOrder(root.left);postOrder(root.right);System.out.print(root.val );}//非递归后序遍历void postOrderNor(TreeNode root){if (root null){return;}StackTreeNode stack new Stack();TreeNode cur root;TreeNode prev null;while(cur ! null || !stack.isEmpty()){while(cur ! null) {stack.push(cur);cur cur.left;}}TreeNode top stack.peek();if (top.right null || top.right prev){System.out.print(top.val );stack.pop();prev top;}else{cur top.right;}//先创建栈让currootcur不等于空或者栈不为空当cur不等于空时让cur入栈,然后让curcur.left//直到当cur等于空时,定义prevnull让top瞄一眼栈顶元素如果等于空或者top.rightprev进入循环// 循环内打印top.val并且出栈然后让prevtop否则让curcur.right}
