二叉树相关OJ题练习
1. 二叉树的最大深度。OJ链接
class Solution {public int maxDepth(TreeNode root) {if (root == null) {return 0;}int leftHeight = maxDepth(root.left);int rightHeight = maxDepth(root.right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}
}2. 检查两棵树是否相同。OJ链接
如下图所示实例即为两棵相同的树。
如下图就是两棵不同的树：结构不同。
如下图也是两棵不同的树：值不同。
注意题目要求：结构上相同，即左右子树及其值要相同。
首先可以先判断结构上是否相同，如果两树的相同位置的子树一个为空一个为空就两树就不同，如果两树的相同位置的子树都为空，两树相同，如果两树相同位置但子树都不为空，那么判断里面的值是否一样，值一样就往下判断它的左右子树是否相同，相同了两棵树才完全相同。
class Solution {//时间复杂度：O(min(M,N))public boolean isSameTree(TreeNode p, TreeNode q) {if(p != null && q == null || p == null && q != null){return false;}if(p == null && q == null){return true;}if(p.val != q.val){return false;}return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);}
}3. 另一棵树的子树。OJ链接
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
class Solution {//时间复杂度：root：有r个节点 subRoot：有s个节点 O(|s|*|t|)public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(root == null || subRoot == null){return false;}//1. 判断两棵树是不是相同的树if(isSameTree(root, subRoot)){return true;}//2. subRoot是不是root的左子树if(isSubtree(root.left, subRoot)){return true;}//3. subRoot是不是root的右子树if(isSubtree(root.right, subRoot)){return true;}return false;}public boolean isSameTree(TreeNode p, TreeNode q) {//详见上题代码}
}4. 反转二叉树。OJ链接
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
class Solution {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;}
}5. 平衡二叉树。OJ链接
一颗高度平衡的二叉树的定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
时间复杂度为O(n^2)：
class Solution {public int maxDepth(TreeNode root) {//详见上文求二叉树深度}public boolean isBalanced(TreeNode root) {if(root == null){return true;}int leftH = maxDepth(root.left);int rightH = maxDepth(root.right);return Math.abs(leftH - rightH) < 2 &&isBalanced(root.left) && isBalanced(root.right);}
}以上代码，会有重复求深度的问题，浪费了时间，改进代码，使时间复杂度为O(n)：
class Solution {public int maxDepth(TreeNode root) {if (root == null) {return 0;}int leftHeight = maxDepth(root.left);if (leftHeight < 0) {return -1;}int rightHeight = maxDepth(root.right);if(leftHeight >= 0 && rightHeight >= 0 &&Math.abs(leftHeight - rightHeight) <= 1){return Math.max(leftHeight,rightHeight) + 1; // 返回真实的高度}else{return -1;}}public boolean isBalanced(TreeNode root) {if(root == null){return true;}return maxDepth(root) >= 0;}
}6. 对称二叉树。OJ链接
class Solution {public boolean isSymmetric(TreeNode root) {if(root == null){return true;}return isSymmetricChild(root.left, root.right);}private 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);}
}7. 二叉树的层序遍历。OJ链接
题目中，要求把每一层的值放进list中，所以问题的焦点在于如何确定二叉树的这一层。
我们通过队列不断的出队入队可以得到想要的结果，下面以下图为例讲解。
当根不为空时将其（即A）放入队列，然后队列不为空，此时队列中有一个节点，这个队列的size为1，将其弹出给cur，同时这一个节点作为新申请一个list的第一层，size--为0。然后再把cur的左和右放进队列（即B、C），那么此时队列不为空且size为2，于是接下来这一层list中就放B和C。执行同样的操作，把B弹出给cur同时也放进新list中，然后将B的左和右放进队列，此时size--后为1，再将C放进list，size--为0，此时这个list就是第二层，然后将C的左右放进队列，这时队列中就是第三层了，以此类推。
class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> list = new ArrayList<>();if (root == null) {return list;}Queue<TreeNode> qu = new LinkedList<>();qu.offer(root);while (!qu.isEmpty()) {int size = qu.size();List<Integer> tmp = new ArrayList<>();while (size > 0) {TreeNode cur = qu.poll();size--;tmp.add(cur.val);if (cur.left != null) {qu.offer(cur.left);}if (cur.right != null) {qu.offer(cur.right);}}list.add(tmp);//易漏注意！}return list;}
}8. 二叉树的构建及遍历。OJ链接
编一个程序，读入用户输入的一串先序遍历（即前序遍历）字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
题干中可以读到，#确定了空树的位置，所以很容易画出该二叉树。
由于题目给的是先根遍历的字符串，所以需要先拿到字符串的每一个字符。对字符串进行遍历，如果拿到的不是“#”而是字符，就表明拿到的是节点。
import java.util.Scanner;class TreeNode {public char val;public TreeNode left;public TreeNode right;public TreeNode(char val) {this.val = val;}
}// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseString str = in.nextLine();TreeNode root = createTree(str);//中序遍历这棵二叉树inOrder(root);}}public static void inOrder(TreeNode root) {if (root == null) {return;}inOrder(root.left);System.out.print(root.val + " ");inOrder(root.right);}private static int i = 0;private static TreeNode createTree(String str) {TreeNode root = null;if (str.charAt(i) != '#') {root = new TreeNode(str.charAt(i));i++;root.left = createTree(str);root.right = createTree(str);} else {i++;}return root;}
}9. 二叉树的最近公共祖先。OJ链接
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
第一种思路：利用两个栈分别存储祖先节点到p和祖先节点到p的节点，比较两栈大小并将大的栈弹出元素直至两栈大小相同，然后两栈再同时弹出元素，当弹出的元素相同时即为公共祖先。
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null || p == null || q == null){return null;}Stack<TreeNode> stack1 = new Stack<>();getPath(root, p, stack1);Stack<TreeNode> stack2 = new Stack<>();getPath(root, q, stack2);int size1 = stack1.size();int size2 = stack2.size();if(size1 > size2){int size = size1 - size2;while(size > 0){stack1.pop();size--;}}else{int size = size2 - size1;while(size > 0){stack2.pop();size--;}}//两栈中一定是相同的节点个数while(stack1.peek() != stack2.peek()){stack1.pop();stack2.pop();}return stack1.peek();}private boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> 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 == true){return true;}boolean flg2 = getPath(root.right, node, stack);if(flg2 == true){return true;}stack.pop();return false;}
}第二种思路： 二叉搜索树
二叉搜索树的概念：根节点比左子树大，比右子树小（递归的），当对其进行中序遍历时结果是有序的。
所以如果有x、y两个节点，寻找它们的公共祖先，就可能出现如下的情况：
（1）x、y其中一个是根节点，公共祖先就是x或y；
（2）x、y在根节点两侧，公共祖先就是root；
（3）x、y在root的左子树或者在root右子树中。
将本题代入上述各个情况：
class Solution {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 if(rightTree != null){return rightTree;}else{return null;}}
}10. 二叉搜索树转化成排序的双向链表。OJ链接
public class Solution {TreeNode prev = null;public TreeNode Convert(TreeNode pRootOfTree) {if(pRootOfTree == null){return null;}convertChild(pRootOfTree);TreeNode head = pRootOfTree;while(head.left != null){head = head.left;}return head;}private void convertChild(TreeNode pCur){if(pCur == null){return;}convertChild(pCur.left);pCur.left = prev;if(prev != null){prev.right = pCur;}prev = pCur;convertChild(pCur.right);}
}11. 二叉树前序遍历非递归实现。OJ链接、
需要定义一个引用cur，通过cur来遍历这棵树。
首先有一个栈，定义一个cur指向root。
如果cur不为空，就把cur当前所指向的节点A放入栈中，同时把A打印。
接下来cur往左边走为B，将B入栈并打印。然后再往左走为D，将D入栈并打印。
再往左走，cur为空了。这时对于D这棵树的根走完了，左也走完了，接下来就看D的右边，这时弹出D给到top，然后让cur指向当前D的右边，也为空，那么相当于D这棵树左走完了，然后再弹出B给到top，让cur指向B的右。以此类推。
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> ret = new ArrayList<>();TreeNode cur = root;Stack<TreeNode> stack = new Stack<>();while (cur != null || !stack.isEmpty()) {while (cur != null) {stack.push(cur);ret.add(cur.val);cur = cur.left;}TreeNode top = stack.pop();cur = top.right;}return ret;}
}12. 二叉树中序遍历非递归实现。OJ链接
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> ret = new ArrayList<>();TreeNode cur = root;Stack<TreeNode> stack = new Stack<>();while (cur != null || !stack.isEmpty()) {while (cur != null) {stack.push(cur);cur = cur.left;}TreeNode top = stack.pop();ret.add(top.val);cur = top.right;}return ret;}
}13. 二叉树后序遍历非递归实现。OJ链接
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> ret = new ArrayList<>();TreeNode cur = root;Stack<TreeNode> stack = new Stack<>();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) {ret.add(top.val);stack.pop();prev = top;} else {cur = top.right;}}return ret;}
}14. 根据前中序遍历构建二叉树。OJ链接
class Solution {public int preIndex = 0;public TreeNode buildTree(int[] preorder, int[] inorder) {return buildTreeChild(preorder, inorder, 0, inorder.length-1);}private TreeNode buildTreeChild(int[] preorder, int[] inorder, int inbegin, int inend){//1. 判断当前根节点是否有左子树或者右子树if(inbegin > inend){return null;}TreeNode root = new TreeNode(preorder[preIndex]);//2. 找到root在中序遍历的位置int rootIndex = findIndex(inorder, inbegin, inend, preorder[preIndex]);preIndex++;if(rootIndex == -1){return null;}//3. 构建左子树和右子树root.left = buildTreeChild(preorder, inorder, inbegin, rootIndex-1);root.right = buildTreeChild(preorder, inorder, rootIndex+1, inend);return root;}private int findIndex(int[] inorder, int inbegin, int inend, int val){for(int i = inbegin; i <= inend; i++){if(inorder[i] == val){return i;}}return -1;}
}15. 根据中后序遍历构建二叉树。OJ链接
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);}private TreeNode buildTreeChild(int[] postorder, int[] inorder, int inbegin, int inend){//1. 判断当前根节点是否有左子树或者右子树if(inbegin > inend){return null;}TreeNode root = new TreeNode(postorder[postIndex]);//2. 找到root在中序遍历的位置int rootIndex = findIndex(inorder, inbegin, inend, postorder[postIndex]);postIndex--;if(rootIndex == -1){return null;}//3. 构建左子树和右子树root.right = buildTreeChild(postorder, inorder, rootIndex+1, inend);root.left = buildTreeChild(postorder, inorder, inbegin, rootIndex-1);return root;}private int findIndex(int[] inorder, int inbegin, int inend, int val){for(int i = inbegin; i <= inend; i++){if(inorder[i] == val){return i;}}return -1;}
}16. 二叉树创建字符串。OJ链接
class Solution {public String tree2str(TreeNode root) {StringBuilder stringBuilder = new StringBuilder();tree2strChild(root, stringBuilder);return stringBuilder.toString();}public void tree2strChild(TreeNode t, StringBuilder stringBuilder){if(t == null){return;}stringBuilder.append(t.val);if(t.left != null){stringBuilder.append("(");tree2strChild(t.left, stringBuilder);stringBuilder.append(")");}else{if(t.right == null){return;}else{stringBuilder.append("()");}}if(t.right == null){return;}else{stringBuilder.append("(");tree2strChild(t.right, stringBuilder);stringBuilder.append(")");}}
}