“手撕”二叉树的OJ习题

故事的开头，我们先来三道不是oj的开胃菜，练练手感，后面9道都是OJ题。

目录

第一题

第二题

第三题

第四题

第五题

第六题

第七题 

第八题

第九题

第十题

第十一题 

第一题

二叉树前序非递归遍历实现 。

 首先我们需要一个栈来存放二叉树里面的元素，定义一个Tree Node类型的cur来指向要入栈的元素，然后一直往栈里放root.left，边放边打印，全部放完就出栈。最后让cur指向栈顶元素，也就是回退到不为空的节点，再遍历right。！stack.isEmpty()就是栈里面不为空，就不用再写一遍while的打印循环了。

public void preOrderNot(TreeNode root) {Stack<TreeNode> 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) {Stack<TreeNode> 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) {Stack<TreeNode> stack = new Stack<>();if (root == null) {return;}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||prev==top.right) {stack.pop();System.out.print(top.val + " ");prev=top;} 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(root==null){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(root==null){return null;}TreeNode tmp=root.left;root.left=root.right;root.right=tmp;invertTree(root.left);invertTree(root.right);return root;}

第七题 

 判断一颗二叉树是否是平衡二叉树。OJ链接

什么是平衡二叉树？就是左子树和右子树高度差必须小于等于1。左子树如果树为空，平衡true；定义左高度和右高度，用getHeight方法获取左右树的高度，然后用绝对值方法abs来求高度差，只要左子树和右子树高度差小于1，并且左子树自己平衡，右子树也平衡才true。

public boolean isBalanced(TreeNode root) {if(root==null){return true;}int leftH=getHeight(root.left);int rightH=getHeight(root.right);return Math.abs(leftH-rightH)<=1&&isBalanced(root.left)&&isBalanced(root.right);}// 获取二叉树的高度public int getHeight(TreeNode root) {if(root==null){return 0;}int leftH=getHeight(root.left);int rightH=getHeight(root.right);return Math.max(leftH,rightH)+1;}

第八题

对称二叉树。 OJ链接

如果root==null则是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 TreeNode（charAt（i））进去接到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链接

利用队列在装这些元素，如果root=null直接返回。不为空，则入队一个root，队列不为空的话把这个打印出来，出队，如果这个root左右子树不为空，入队，然后进行循环，直到一整颗树被打印完。为什么用队列而不用栈呢？如果用栈就从 右往左打印了，显然不符合层序遍历的规律。

public void levelOrder(TreeNode root){Queue<TreeNode> queue=new LinkedList<>();if(root==null){return;}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);}}System.out.println();}

第十一题 

 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先 。OJ链接

也是利用结构判断，如果root=null，返回null；如果p和q任意有个人在root，直接返回root；如果没有，继续递归，看看左右子树：如果左右子树都找得到p或q，那么说明左右子树各有一个，它的祖先必然是root；如果都在左子树，找到一个就返回，都在右子树，找到一个就返回。 

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.right,p,q);//左子树和右子树各一个if(leftTree!=null&&rightTree!=null){return root;}//都在左子树,找到一个就返回else if(leftTree!=null){return leftTree;}//都在右子树，找到一个就返回else{return rightTree;}}