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

﹏ヽ暗。殇╰゛Y 2023-10-14 00:24 10阅读 0赞

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