算法基础学习2 算法基础学习2

一、二叉树对于每次递归遍历的时候，会产生一个遍历序，也就是对于一个节点间，会进行三次访问
可以在这三次中改变打印的位置。从而形成先序，中序，后序遍历。

文章图片

代码：

public static void OrderRecur(Node head) { if (head == null) { return; } //第一次访问节点就输出，System.out.print(head.value + " "); OrderRecur(head.left); //第二次访问节点输出 System.out.print(head.value + " "); OrderRecur(head.right); //第三次访问节点输出System.out.print(head.value + " "); }

非递归遍历先序

/** * 准备一个栈，将root压入栈 * 1.弹出栈元素 * 2.打印 * 3.先压入右节点，再压入左节点（如果有的话） * 4.循环上述步骤 * @param root */ public static void PreOrderWithoutRecursion(Node root){ //栈 Stack nodes = new Stack<>(); nodes.push(root); while (!nodes.isEmpty()){ //弹出 Node pop = nodes.pop(); System.out.println(pop.value); //压入孩子节点 if (pop.right != null){ nodes.push(pop.right); } if (pop.left != null){ nodes.push(pop.left); } } }

中序

/** * 准备一个栈，将root压入栈 * 1.一直将节点的左孩子压入栈中 * 2.弹出打印 * 3.如果弹出的存在右孩子，也将右孩子的左孩子一直压入栈 * 4，循环 */ public static void InOrderWithoutRecursion(Node root){ //栈 Stack nodes = new Stack<>(); while (! nodes.isEmpty() || root != null){ //1.将左孩子全部压入栈中 if (root != null){ nodes.push(root); root = root.left; } else { //2.弹出，打印 root = nodes.pop(); System.out.print(root.value+" "); //继续右孩子 root = root.right; } } }

后续

/** * 准备两个栈，将root压入栈 * 1.弹出，压入到2栈中 * 2.将左孩子压入1栈 * 3.将右孩子压入1栈 * 4.一直到1栈为空，输出2栈元素 */ public static void PosOrderWithoutRecursion(Node root){ Stack stack1 = new Stack<>(); Stack stack2 = new Stack<>(); stack1.push(root); while (!stack1.isEmpty()){ //弹出，压缩2栈 Node pop = stack1.pop(); stack2.push(pop); //分别压入左孩子和有孩子 if (pop.left != null){ stack1.push(pop.left); } if (pop.right != null){ stack1.push(pop.right); } } while ( !stack2.isEmpty()){ Node pop = stack2.pop(); System.out.print(pop.value+" "); } }

层次

/** * 层次遍历 * 准备一个队列，加入根节点 * 1，弹出，打印 * 2.加入左孩子 * 3.加入右孩子 * 4.循环 */ public static void WithOrder(Node root){ Queue queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()){ //弹出打印 Node poll = queue.poll(); System.out.print(poll.value+" "); if (poll.left != null){ queue.add(poll.left); } if (poll.right != null){ queue.add(poll.right); } } }

题获取最大宽度
使用层次遍历

/** * 获取最大宽度将根节点加入到队列中 * 准备一个队列，准备一个hashMap,用来存储各个节点处于第几层 * 1.先层次遍历，在添加节点，要向map中添加节点处在都第几层 * 2.在层次遍历中，如果发现节点的层数和要统计的层数相同，就当前层数节点数++，并将最大值保留 *不同则说明已经统计到下一层了，将统计的层数更新，将当前节点数更新 */ public static int getMaxWith(Node root){ Queue queue = new LinkedList<>(); //各个节点的层数 Map map = new HashMap<>(); queue.add(root); //root在第一层 map.put(root,1); //当前层数 int curLevel = 1; //当前层数的节点 int curLevelNodes = 0; //最大值 int max = Integer.MIN_VALUE; while (!queue.isEmpty()){ Node poll = queue.poll(); int curNodeLevel = map.get(poll); //当前节点的层数等于当前层数 if (curNodeLevel == curLevel){ //节点数++ curLevelNodes++; } //已经到下一层 else { //更新max max = Math.max(max,curLevelNodes); //更新层数 curLevel++; //初始化当前层数节点数 curLevelNodes = 1; } if (poll.left != null){ map.put(poll.left, curLevel+1); queue.add(poll.left); } if (poll.right!= null){ map.put(poll.right, curLevel+1); queue.add(poll.right); } } max = Math.max(curLevelNodes,max); return max; }

判断是否为搜索二叉树（左子树值小于根小于右子树）
中序遍历改写
判断是否为完全二叉树

/** * 判断是否为完全二叉树 * 满足两个条件 * 使用层次遍历 * 1.如果节点有右孩子没有左孩子，则不是 * 2.如果不是孩子双全，并且满足第一个条件，那么接下来的节点就都是叶子节点 * @return */ public static boolean isCompletedBinaryTree(Node root){ Queue queue = new LinkedList<>(); queue.add(root); Node leftChird = null; Node rightChird = null; //是否是孩子双全 boolean sigleChild = false; while (! queue.isEmpty()){ Node poll = queue.poll(); leftChird = poll.left; rightChird = poll.right; //如果满足了第一个条件，并且当前节点不是叶节点 //或只有右孩子没有左孩子, //则不是完全二叉树 if (sigleChild && (leftChird != null || rightChird!= null) || (rightChird != null && leftChird == null)){ return false; } if (leftChird != null){ queue.add(leftChird); } if (rightChird != null){ queue.add(rightChird); } //如果孩子不双全,则变为单个节点的状态 if (leftChird == null || rightChird == null){ sigleChild = true; } } return true; }

判断是否为平衡二叉树（模板,递归）

/** * 是否是平衡二叉树 * 平衡二叉树：左子树是平衡二叉树，右子树是平衡二叉树，子树的高度差小于2 * 因此对于子树而言，需要返回两个值，是否是平衡树，以及高度 */ public static ResultType process(Node node){ if (node == null){ return new ResultType(true,0); } ResultType leftResult = process(node.left); ResultType rightResult = process(node.right); //高度 int height = Math.max(leftResult.height, rightResult.height)+1; //平衡 boolean isBlance = Math.abs(leftResult.height- rightResult.height) < 2; return new ResultType(isBlance,height); } public static boolean isBalanceBinaryTreeRecursion(Node root){ ResultType process = process(root); return process.isBlance; } //返回结果封装 public static class ResultType { //是否平衡 private boolean isBlance; //高度 private int height; public ResultType(boolean isBlance, int height) { this.isBlance = isBlance; this.height = height; } }

判断是否为满二叉树（模板，递归）

/** * 判断是否为满二叉树 * 模板：得到height,nodes * (2^height)- 1 = nodes */ public static boolean isFullBinaryTree(Node root){ if (root == null){ return true; } ResultData resultData = https://www.it610.com/article/f(root); int height = resultData.height; int nodes = resultData.nodes; boolean isFull = (1 << height)-1 == nodes; return isFull; } public static ResultData f(Node node){ if (node == null){ //空树高度0，节点数0 return new ResultData(0,0); } ResultData leftRes = f(node.left); ResultData ritRes = f(node.right); int height = Math.max(leftRes.height, ritRes.height); int nodes = leftRes.nodes+ ritRes.nodes; return new ResultData(height,nodes); } //满二叉树封装结果 public static class ResultData{ private int height; private int nodes; public ResultData(int height, int nodes) { this.height = height; this.nodes = nodes; } }

最低公共祖先节点
给定两个二叉树的节点node1和node2，找到他们的最低公共祖先节点

/** * 准备一个map,存储各个节点的父节点 * 准备一个set,将n1链的父节点进行存储 * 遍历n2的父节点过程中，如果在set中存在，则直接返回该点就是最终lca */ public static Node LCA(Node root,Node n1,Node n2){ //存放对应父节点 HashMap map = new HashMap<>(); map.put(root,root); process(root,map); //存放n1的父节点链 HashSet set = new HashSet<>(); Node cur1 = n1; Node cur2 = n2; //一直到根节点 while (cur1 != map.get(cur1)){ set.add(cur1); cur1 = map.get(cur1); } //加入根节点 set.add(root); //在链中找n2的父节点们 while (!set.contains(cur2)){ cur2 = map.get(cur2); } return cur2; } //存储父节点 public static void process(Node node, HashMap map){ if (node == null){ return; } //添加父节点 map.put(node.left,node); map.put(node.right,node); process(node.left,map); process(node.right,map); }

方法二

/** * lca方法二 * 对于每一个节点来说 * 如果左右子树中存在n1或n2则返回 * 不存在则返回空 * 到根节点的时候，也就是回溯到最上层时候，如果左子树不存在n1和n2，那么返回右子树最先出现的n1或n2就是lca * 如果n1和n2分别出现在左右子树 * 那么根节点就是lca */ public static Node LCA2(Node root,Node n1,Node n2){ if (root == null || root == n1 || root == n2){ return root; } //寻找孩子 Node left = LCA2(root.left, n1, n2); Node right = LCA2(root.right, n1, n2); //如果n1和n2是两个分支中 if (left != null && right != null){ return root; } return left!=null?left:right; }

折纸问题
请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。
此时折痕是凹下去的，即折痕突起的方向指向纸条的背面。如果从纸条的下边向上方连续对折2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。
给定一个输入参数N，代表纸条都从下边向上方连续对折N次。
请从上到下打印所有折痕的方向。
【算法基础学习2】例如:N=1时，打印: down N=2时，打印: down down up

public static void main(String[] args) { int N = 3; paperFold(N); } public static void process(int level,int N, boolean down){ if (level > N){ return; } process(level+1,N,true); System.out.println(down?"down":"up"); process(level+1,N,false); } public static void paperFold(int N){ process(1,N,true); }