算法练习（2）：牛客在线编程03 二叉树

package jz.bm;import jz.TreeNode;import java.util.*;public class bm3 {/*** BM23 二叉树的前序遍历*/public int[] preorderTraversal (TreeNode root) {ArrayList<Integer> list = new ArrayList<>();preOrder(root, list);int[] res = new int[list.size()];for (int i = 0; i < list.size(); i++) {res[i] = list.get(i);}return res;}private void preOrder(TreeNode root, ArrayList<Integer> list) {if (root != null) {list.add(root.val);preOrder(root.left, list);preOrder(root.right, list);}}/*** BM24 二叉树的中序遍历*/public int[] inorderTraversal (TreeNode root) {ArrayList<Integer> list = new ArrayList<>();inOrder(root, list);int[] res = new int[list.size()];for (int i = 0; i < list.size(); i++) {res[i] = list.get(i);}return res;}private void inOrder(TreeNode root, ArrayList<Integer> list) {if (root != null) {inOrder(root.left, list);list.add(root.val);inOrder(root.right, list);}}/*** BM25 二叉树的后序遍历*/public int[] postorderTraversal (TreeNode root) {ArrayList<Integer> list = new ArrayList<>();postOrder(root, list);int[] res = new int[list.size()];for (int i = 0; i < list.size(); i++) {res[i] = list.get(i);}return res;}private void postOrder(TreeNode root, ArrayList<Integer> list) {if (root != null) {postOrder(root.left, list);postOrder(root.right, list);list.add(root.val);}}/*** BM26 求二叉树的层序遍历*/public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {ArrayList<ArrayList<Integer>> res = new ArrayList<>();if (root == null) {return res;}Queue<TreeNode> queue = new LinkedList<>();queue.add(root);while (!queue.isEmpty()) {int n = queue.size();ArrayList<Integer> list = new ArrayList<>();for (int i = 0; i < n; i++) {TreeNode cur = queue.poll();list.add(cur.val);if (cur.left != null) {queue.add(cur.left);}if (cur.right != null) {queue.add(cur.right);}}res.add(list);}return res;}/*** BM27 按之字形顺序打印二叉树*/public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {ArrayList<ArrayList<Integer>> res = new ArrayList<>();if (pRoot == null) {return res;}Queue<TreeNode> queue = new LinkedList<>();queue.add(pRoot);boolean flag = false;while (!queue.isEmpty()) {int n = queue.size();ArrayList<Integer> list = new ArrayList<>();for (int i = 0; i < n; i++) {TreeNode cur = queue.poll();list.add(cur.val);if (cur.left != null) {queue.add(cur.left);}if (cur.right != null) {queue.add(cur.right);}}if (flag) {Collections.reverse(list);}flag = !flag;res.add(list);}return res;}/*** BM28 二叉树的最大深度*/int max = 0;public int maxDepth (TreeNode root) {dfs28(root, 0);return max;}private void dfs28(TreeNode root, int depth) {if (root != null) {depth += 1;max = Math.max(max, depth);dfs28(root.left, depth);dfs28(root.right, depth);}}/*** BM29 二叉树中和为某一值的路径(一)*/boolean hasPath = false;public boolean hasPathSum (TreeNode root, int sum) {dfs29(root, sum);return hasPath;}private void dfs29(TreeNode root, int cur) {if (root != null) {cur -= root.val;if (root.left == null && root.right == null && cur == 0) {hasPath = true;return;}dfs29(root.left, cur);dfs29(root.right, cur);}}/*** BM30 二叉搜索树与双向链表*/TreeNode head;TreeNode pre;public TreeNode Convert(TreeNode pRootOfTree) {if (pRootOfTree != null) {Convert(pRootOfTree.left);if (pre == null) {head = pRootOfTree;} else {pre.right = pRootOfTree;pRootOfTree.left = pre;}pre = pRootOfTree;Convert(pRootOfTree.right);}return head;}/*** BM31 对称的二叉树*/public boolean isSymmetrical (TreeNode pRoot) {if (pRoot != null) {return mirror(pRoot.left, pRoot.right);} else {return true;}}private boolean mirror(TreeNode left, TreeNode right) {if (left == null && right == null) {return true;}if (right == null || left == null || left.val != right.val) {return false;}return mirror(left.left, right.right) && mirror(left.right, right.left);}/*** BM32 合并二叉树*/public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {if (t1 == null) {return t2;}if (t2 == null) {return t1;}t1.val = t1.val + t2.val;t1.left = mergeTrees(t1.left, t2.left);t1.right = mergeTrees(t1.right, t2.right);return t1;}/*** BM34 判断是不是二叉搜索树*/boolean res34 = true;TreeNode pre34 = null;public boolean isValidBST (TreeNode root) {inOrder(root);return res34;}private void inOrder(TreeNode root) {if (root != null) {inOrder(root.left);if (pre34 == null) {pre34 = root;} else {if (root.val <= pre34.val) {res34 = false;}}pre34 = root;inOrder(root.right);}}/*** BM35 判断是不是完全二叉树*/public boolean isCompleteTree (TreeNode root) {if (root == null) {return true;}Queue<TreeNode> queue = new LinkedList<>();queue.add(root);boolean hasNull = false;while (!queue.isEmpty()) {TreeNode cur = queue.poll();if (cur == null) {hasNull = true; //遇到空的节点} else {//空的节点后面有非空的节点if (hasNull) {return false;}queue.add(cur.left);queue.add(cur.right);}}return true;}/*** BM36 判断是不是平衡二叉树*/public boolean IsBalanced_Solution (TreeNode pRoot) {if (pRoot == null) {return true;}return IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right) && Math.abs(dfs36(pRoot.left) - dfs36(pRoot.right)) <= 1;}private int dfs36(TreeNode pRoot) {if (pRoot != null) {return Math.max(dfs36(pRoot.left), dfs36(pRoot.right)) + 1;}return 0;}/*** BM37 二叉搜索树的最近公共祖先*/public int lowestCommonAncestor (TreeNode root, int p, int q) {if (root == null) {return -1;}if ((p <= root.val && root.val <= q) || (q <= root.val && root.val <= p)) {return root.val;} else if (p <= root.val && q <= root.val) {return lowestCommonAncestor(root.left, p, q);} else {return lowestCommonAncestor(root.right, p, q);}}/*** BM38 在二叉树中找到两个节点的最近公共祖先*/public int lowestCommonAncestor1 (TreeNode root, int o1, int o2) {if (root == null) {return -1;}if (o1 == root.val || o2 == root.val) {return root.val;}int left = lowestCommonAncestor1(root.left, o1, o2);int right = lowestCommonAncestor1(root.right, o1, o2);if (left == -1) {return right;}if (right == -1) {return left;}//即不是左也不是右，只能是当前节点return root.val;}/*** BM40 重建二叉树*/public TreeNode reConstructBinaryTree (int[] preOrder, int[] vinOrder) {if (preOrder.length == 0 || vinOrder.length == 0) {return null;}TreeNode head = new TreeNode(preOrder[0]);int index = getIndex(preOrder[0],vinOrder);head.left = reConstructBinaryTree(Arrays.copyOfRange(preOrder, 1, index + 1), Arrays.copyOfRange(vinOrder, 0, index));head.right = reConstructBinaryTree(Arrays.copyOfRange(preOrder, index + 1, preOrder.length), Arrays.copyOfRange(vinOrder, index + 1, vinOrder.length));return head;}private int getIndex(int head, int[] vinOrder) {for (int i = 0; i < vinOrder.length; i++) {if (head == vinOrder[i]) {return i;}}return -1;}/*** BM41 输出二叉树的右视图*/public int[] solve (int[] preOrder, int[] inOrder) {TreeNode head = reConstructBinaryTree(preOrder, inOrder);if (head == null) {return new int[0];}ArrayList<Integer> list = new ArrayList<>();Queue<TreeNode> queue = new LinkedList<>();queue.add(head);while (!queue.isEmpty()) {int n = queue.size();for (int i = 0; i < n; i++) {TreeNode cur = queue.poll();if (i == n - 1) {list.add(cur.val);}if (cur.left != null) {queue.add(cur.left);}if (cur.right != null) {queue.add(cur.right);}}}int[] res = new int[list.size()];for (int i = 0; i < list.size(); i++) {res[i] = list.get(i);}return res;}
}