【数据结构】二叉树

• 1 相同的树
• 2 对称二叉树
• 3 二叉树的最大深度
• 4 从前序与中序遍历序列构造二叉树
• 5 二叉树的层序遍历
• 6 是否是平衡二叉树
• 7 路径总和
• 8 路径总和 II
• 9 是否是二叉搜索树

public class Code02_SameTree {

    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }

    public static boolean isSameTree(TreeNode p, TreeNode q) {
        // 一个为空 一个不为空
        if (p == null ^ q == null) {
            return false;
        }
        
        // 都为空
        if (p == null) {
            return true;
        }

        // 值相同且左右子树都相同
        return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

public class Code03_SymmetricTree {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static boolean isSymmetric(TreeNode root) {
        return isMirror(root, root);
    }

    private static boolean isMirror(TreeNode p, TreeNode q) {
        if (p == null ^ q == null) {
            return false;
        }

        if (p == null) {
            return true;
        }

        return p.val == q.val && isMirror(p.left, q.right) && isMirror(p.right, q.left);
    }
}

public class Code04_MaximumDepthOfBinaryTree {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

public class Code05_ConstructBinaryTreeFromPreorderAndInorderTraversal {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null || preorder.length != inorder.length) {
            return null;
        }

        Map inMap = new HashMap<>(inorder.length);
        for (int i = 0; i < inorder.length; i++) {
            inMap.put(inorder[i], i);
        }

        return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, inMap);
    }

    public static TreeNode buildTree(int[] preorder, int pL, int pR,
                                     int[] inorder, int iL, int iR, Map inMap) {
        if (pL > pR) {
            return null;
        }

        // 只有一个值
        TreeNode head = new TreeNode(preorder[pL]);
        if (pL == pR) {
            return head;
        }

        // 中序遍历的根节点索引
        Integer iRoot = inMap.get(preorder[pL]);
        head.left = buildTree(preorder, pL + 1, pL + iRoot - iL, inorder, iL, iRoot - 1, inMap);
        head.right = buildTree(preorder, pL + iRoot - iL + 1, pR, inorder, iRoot + 1, iR, inMap);

        return head;
    }
}

public class Code02_BalancedBinaryTree {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static class Info {
        
        private int height;

        
        private boolean isBalanced;

        public Info(int height, boolean isBalanced) {
            this.height = height;
            this.isBalanced = isBalanced;
        }
    }

    public static boolean isBalanced(TreeNode root) {
        return process(root).isBalanced;
    }

    
    public static Info process(TreeNode node) {
        if (node == null) {
            return new Info(0, true);
        }

        // 左右子树的平衡信息
        Info lInfo = process(node.left);
        Info rInfo = process(node.right);

        // 当前节点高度信息
        int height = Math.max(lInfo.height, rInfo.height) + 1;
        // 当前节点平衡信息
        boolean isBalanced = lInfo.isBalanced && rInfo.isBalanced && Math.abs(lInfo.height - rInfo.height) < 2;

        return new Info(height, isBalanced);
    }
}

public class Code02_BalancedBinaryTree {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static class Info {
        
        private int height;

        
        private boolean isBalanced;

        public Info(int height, boolean isBalanced) {
            this.height = height;
            this.isBalanced = isBalanced;
        }
    }

    public static boolean isBalanced(TreeNode root) {
        return process(root).isBalanced;
    }

    
    public static Info process(TreeNode node) {
        if (node == null) {
            return new Info(0, true);
        }

        // 左右子树的平衡信息
        Info lInfo = process(node.left);
        Info rInfo = process(node.right);

        // 当前节点高度信息
        int height = Math.max(lInfo.height, rInfo.height) + 1;
        // 当前节点平衡信息
        boolean isBalanced = lInfo.isBalanced && rInfo.isBalanced && Math.abs(lInfo.height - rInfo.height) < 2;

        return new Info(height, isBalanced);
    }
}

public class Code03_PathSum {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static boolean isSum;

    public static boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }

        isSum = false;
        process(root, 0, targetSum);
        return isSum;
    }

    
    public static void process(TreeNode node, int preSum, int targetSum) {
        // 叶子节点
        if (node.left == null && node.right == null) {
            if (preSum + node.val == targetSum) {
                isSum = true;
            }
            // 叶子返回
            return;
        }

        // 路径和
        preSum += node.val;
        if (node.left != null) {
            process(node.left, preSum, targetSum);
        }
        if (node.right != null) {
            process(node.right, preSum, targetSum);
        }
    }

    
    public static boolean process(TreeNode node, int sum) {
        // 叶子节点
        if (node.left == null && node.right == null) {
            return node.val == sum;
        }

        // 非叶子节点
        boolean ans = node.left != null && process(node.left, sum - node.val);
        ans |= (node.right != null && process(node.right, sum - node.val));
        return ans;
    }
}

public class Code04_PathSumII {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static List> pathSum(TreeNode root, int targetSum) {
        List> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }

        process(root, new ArrayList<>(), 0, targetSum, ans);
        return ans;
    }

    public static void process(TreeNode node, List path,
                               int preSum, int targetSum, List> ans) {
        // 叶子节点
        if (node.left == null && node.right == null) {
            if (node.val + preSum == targetSum) {
                path.add(node.val);
                ans.add(new ArrayList<>(path));
                // 恢复路径
                path.remove(path.size() - 1);
            }
            return;
        }

        // 非叶子节点
        path.add(node.val);
        preSum += node.val;
        if (node.left != null) {
            process(node.left, path, preSum, targetSum, ans);
        }
        if (node.right != null) {
            process(node.right, path, preSum, targetSum, ans);
        }
        // 恢复路径
        path.remove(path.size() - 1);
    }
}

public class Code05_IsBinarySearchTree {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static class Info {
        private boolean isBST;
        private int max;
        private int min;

        public Info(boolean isBST, int max, int min) {
            this.isBST = isBST;
            this.max = max;
            this.min = min;
        }
    }

    public static boolean isValidBST(TreeNode node) {
        if (node == null) {
            return true;
        }

        return process(node).isBST;
    }

    public static Info process(TreeNode node) {
        if (node == null) {
            return null;
        }

        Info lInfo = process(node.left);
        Info rInfo = process(node.right);

        // 当前节点的最大最小值
        int max = node.val;
        int min = node.val;
        if (lInfo != null) {
            max = Math.max(lInfo.max, max);
            min = Math.min(lInfo.min, min);
        }
        if (rInfo != null) {
            max = Math.max(rInfo.max, max);
            min = Math.min(rInfo.min, min);
        }


        boolean isLeftBST = lInfo == null || lInfo.isBST;
        boolean isRightBSt = rInfo == null || rInfo.isBST;
        boolean isLeftMaxLess = lInfo == null || lInfo.max < node.val;
        boolean isRightMinMore = rInfo == null || rInfo.min > node.val;

        boolean isBST = isLeftBST && isRightBSt && isLeftMaxLess && isRightMinMore;

        return new Info(isBST, max, min);
    }
}