Java(二十五)---二叉树的oj题

class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {//1.结构上是否相同if ((p != null && q == null)||(p == null && q != null)){return false;}// 上述if语句不执行，说明 p 和 q 要么都为空，要么都不为空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);}
}

class Solution {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;}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);}
}

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;}
}

class Solution {public boolean isSymmetric(TreeNode root) {if (root == null){return false;}   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);}
}

class Solution {public boolean isBalanced(TreeNode root) {if (root == null){return true;}int leftHight = getHight(root.left);int rightHight = getHight(root.right);return Math.abs(leftHight - rightHight) <= 1 && isBalanced(root.right) && isBalanced(root.left);}public int getHight(TreeNode root){if (root == null){return 0;}int leftHight = getHight(root.left);int rightHight = getHight(root.right);return Math.max(leftHight,rightHight) + 1;}
}

这个方案不是最好的，因为他的时间复杂度是O(n^2)
如何把他改为O(n)呢，那就可以在求子树(height)的时候，进行判断，如果从下往上某个节点的子树不是平衡二叉树，那么这个子树就不可能是平衡二叉树。
改进代码：

class Solution {public boolean isBalanced(TreeNode root) {if (root == null){return true;}return getHight(root)>=0;}public int getHight(TreeNode root){if (root == null){return 0;}int leftHight = getHight(root.left);if (leftHight < 0){return -1;}int rightHight = getHight(root.right);if (rightHight >= 0 &&Math.abs(leftHight - rightHight) <= 1){return Math.max(leftHight,rightHight) + 1;}else{return -1;}}
}

public class Solution {public TreeNode prev;public TreeNode Convert(TreeNode pRootOfTree) {if (pRootOfTree == null){return null;}ConvertChild(pRootOfTree);TreeNode head = pRootOfTree;while(head.left!=null){head = head.left;}return head;}public void ConvertChild(TreeNode root){if (root == null){return;}ConvertChild(root.left);root.left = prev;if (prev != null){prev.right = root;}prev = root;ConvertChild(root.right);}
}

import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
class TreeNode{public char val;public TreeNode left;public TreeNode right;public TreeNode(char ch){this.val = ch;}
}
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);inorderTree(root);}}public static int i =0;public 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;}public static void inorderTree(TreeNode root){if (root == null) return;inorderTree(root.left);System.out.print(root.val+" ");inorderTree(root.right);}
}

我们先写一个返回值是void的层序遍历的方法，等会再写一个返回的是二维列表的方法

    //层序遍历public void levelOrder(TreeNode root){Queue<TreeNode> queue = new LinkedList<>();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();}

题目答案：

class Solution {public List<List<Integer>> levelOrder(TreeNode root){List<List<Integer>> ret = new ArrayList<>();if (root == null){return ret;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int size = queue.size();List<Integer> list = new ArrayList<>();while (size != 0) {TreeNode cur = queue.poll();list.add(cur.val);if (cur.left != null) {queue.offer(cur.left);}if (cur.right != null) {queue.offer(cur.right);}size--;}ret.add(list);}return ret;}
}

这个题的图解颇多，大家可以看码云

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{return rightTree;}}
}

这道题还有一种方法，咱们应用栈把结点存起来，然后在做一次这道题。

class Solution {public boolean getPath(TreeNode root,TreeNode node,Stack<TreeNode> stack){if (root == null){return false;}stack.push(root);if (root == node){return true;}boolean ret = getPath(root.left,node,stack);if (ret) return true;ret = getPath(root.right,node,stack);if (ret) return true;stack.pop();return false;}public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root == null) return null;Stack<TreeNode> stackP = new Stack();Stack<TreeNode> stackQ = new Stack();getPath(root,p,stackP);getPath(root,q,stackQ);int size1 = stackP.size();int size2 = stackQ.size();if (size1 > size2){int size = size1 - size2;while(size != 0){size--;stackP.pop();}}else{int size = size2 - size1;while(size != 0){size--;stackQ.pop();}}while (!stackP.isEmpty() && !stackQ.isEmpty()){if(stackP.peek()==stackQ.peek()){return stackP.peek();}else{stackP.pop();stackQ.pop();}}return null;}
}

class Solution {public int preIndex;public TreeNode buildTree(int[] preorder, int[] inorder) {return buildTreeChild(preorder,inorder,0,inorder.length-1);}public TreeNode buildTreeChild(int[] preorder, int[] inorder,int inbegin,int inend) {//这种情况下 表明 当前root 没有子树了 if(inbegin > inend) {return null;}TreeNode root = new TreeNode(preorder[preIndex]);int rootIndex = findVal(inorder,inbegin,inend,preorder[preIndex]);preIndex++;root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);return root;}private int findVal(int[] inorder,int inbegin,int inend,int val) {for(int i = inbegin ;i <= inend;i++) {if(inorder[i] == val) {return i;}}return -1;}
}

public int postIndex;public TreeNode buildTree(int[] inorder, int[] postorder) {postIndex = postorder.length-1;return buildTreeChild(inorder,postorder,0,inorder.length-1);}public TreeNode buildTreeChild(int[] inorder,int[] postorder,int inbegin,int inend) {//这种情况下 表明 当前root 没有子树了 if(inbegin > inend) {return null;}TreeNode root = new TreeNode(postorder[postIndex]);int rootIndex = findVal(inorder,inbegin,inend,postorder[postIndex]);postIndex--;root.right = buildTreeChild(inorder,postorder,rootIndex+1,inend);root.left = buildTreeChild(inorder,postorder,inbegin,rootIndex-1);return root;}private int findVal(int[] inorder,int inbegin,int inend,int val) {for(int i = inbegin ;i <= inend;i++) {if(inorder[i] == val) {return i;}}return -1;}

    public String tree2str(TreeNode root) {StringBuilder stringBuilder = new StringBuilder();if (root == null){return null;}tree2strChild(root,stringBuilder);return stringBuilder.toString();}public void tree2strChild(TreeNode root,StringBuilder stringBuilder){if (root == null){return;}stringBuilder.append(root.val);if (root.left!=null){stringBuilder.append("(");tree2strChild(root.left,stringBuilder);stringBuilder.append(")");}else{if (root.right == null){return;}else{stringBuilder.append("()");}}if (root.right != null){stringBuilder.append('(');tree2strChild(root.right,stringBuilder);stringBuilder.append(")");}else{return;}}

 public void preOrderNor(TreeNode root){if (root == null){return;}TreeNode cur = root;Stack<TreeNode> stack = new Stack<>();while (cur != null||!stack.empty()){while (cur != null){stack.push(cur);System.out.print(cur.val+" ");cur = cur.left;}TreeNode top = stack.pop();cur = top.right;}System.out.println();}

public void inOrderNor(TreeNode root){if (root == null){return;}TreeNode cur = root;Stack<TreeNode> stack = new Stack<>();while (cur != null||!stack.empty()){while (cur != null){stack.push(cur);cur = cur.left;}TreeNode top = stack.pop();System.out.print(top.val+" ");cur = top.right;}System.out.println();}

public void postOrderNor(TreeNode root){if (root == null){return;}TreeNode cur = root;TreeNode prev = null;Stack<TreeNode> stack = new Stack<>();while (cur != null||!stack.empty()) {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;}}}