剑指offer-问题39

旧城等待， 2022-05-11 15:48 129阅读 0赞

package offer;
    
    /**
     * offer interview 39
     */
    public class Test39 {
    
        private static class BinaryTreeNode{
            int val;
            BinaryTreeNode left;
            BinaryTreeNode right;
    
            public BinaryTreeNode(){}
            public BinaryTreeNode(int val){
                this.val = val;
            }
        }
    
        public static int treeDepth(BinaryTreeNode root){
            if (root == null){
                return 0;
            }
    
            int left = treeDepth(root.left);
            int right = treeDepth(root.right);
    
            return left > right ? (left + 1) : (right  + 1);
        }
    
        public static boolean isBalanced(BinaryTreeNode root){
            if (root == null){
                return true;
            }
    
            int left = treeDepth(root.left);
            int right = treeDepth(root.right);
    
            int diff = left - right;
            if (diff > 1 || diff < -1){
                return false;
            }
    
            return isBalanced(root.left) && isBalanced(root.right);
        }
    
    
        //method 2
        public static boolean isBalanced2(BinaryTreeNode root){
            int[] depth = new int[1];
            return isBalancedHelper(root,depth);
        }
    
        public  static boolean isBalancedHelper(BinaryTreeNode  root, int[] depth){
            if (root == null ){
                depth[0] = 0;
                return true;
            }
    
            int[] left = new int[1];
            int[] right = new int[1];
    
            if (isBalancedHelper(root.left,left) && isBalancedHelper(root.right,right)){
                int diff = left[0] - right[0];
                if (diff >= -1 && diff <= 1){
                    depth[0] = 1 + (left[0] > right[0] ? left[0] : right[0]);
                    return true;
                }
            }
    
            return false;
        }
    
    
    
        // 完全二叉树
        //             1
        //         /      \
        //        2        3
        //       /\       / \
        //      4  5     6   7
        private static void test1() {
            BinaryTreeNode n1 = new BinaryTreeNode(1);
            BinaryTreeNode n2 = new BinaryTreeNode(1);
            BinaryTreeNode n3 = new BinaryTreeNode(1);
            BinaryTreeNode n4 = new BinaryTreeNode(1);
            BinaryTreeNode n5 = new BinaryTreeNode(1);
            BinaryTreeNode n6 = new BinaryTreeNode(1);
            BinaryTreeNode n7 = new BinaryTreeNode(1);
    
            n1.left = n2;
            n1.right = n3;
            n2.left = n4;
            n2.right = n5;
            n3.left = n6;
            n3.right = n7;
    
            System.out.println(isBalanced(n1));
            System.out.println(isBalanced2(n1));
            System.out.println("----------------");
    
        }
    
        // 不是完全二叉树，但是平衡二叉树
        //             1
        //         /      \
        //        2        3
        //       /\         \
        //      4  5         6
        //        /
        //       7
        private static void test2() {
            BinaryTreeNode n1 = new BinaryTreeNode(1);
            BinaryTreeNode n2 = new BinaryTreeNode(1);
            BinaryTreeNode n3 = new BinaryTreeNode(1);
            BinaryTreeNode n4 = new BinaryTreeNode(1);
            BinaryTreeNode n5 = new BinaryTreeNode(1);
            BinaryTreeNode n6 = new BinaryTreeNode(1);
            BinaryTreeNode n7 = new BinaryTreeNode(1);
    
            n1.left = n2;
            n1.right = n3;
            n2.left = n4;
            n2.right = n5;
            n5.left = n7;
            n3.right = n6;
    
    
            System.out.println(isBalanced(n1));
            System.out.println(isBalanced2(n1));
            System.out.println("----------------");
        }
    
        // 不是平衡二叉树
        //             1
        //         /      \
        //        2        3
        //       /\
        //      4  5
        //        /
        //       7
        private static void test3() {
            BinaryTreeNode n1 = new BinaryTreeNode(1);
            BinaryTreeNode n2 = new BinaryTreeNode(1);
            BinaryTreeNode n3 = new BinaryTreeNode(1);
            BinaryTreeNode n4 = new BinaryTreeNode(1);
            BinaryTreeNode n5 = new BinaryTreeNode(1);
            BinaryTreeNode n6 = new BinaryTreeNode(1);
            BinaryTreeNode n7 = new BinaryTreeNode(1);
    
            n1.left = n2;
            n1.right = n3;
            n2.left = n4;
            n2.right = n5;
            n5.left = n7;
    
            System.out.println(isBalanced(n1));
            System.out.println(isBalanced2(n1));
            System.out.println("----------------");
        }
    
        //               1
        //              /
        //             2
        //            /
        //           3
        //          /
        //         4
        //        /
        //       5
        private static void test4() {
            BinaryTreeNode n1 = new BinaryTreeNode(1);
            BinaryTreeNode n2 = new BinaryTreeNode(1);
            BinaryTreeNode n3 = new BinaryTreeNode(1);
            BinaryTreeNode n4 = new BinaryTreeNode(1);
            BinaryTreeNode n5 = new BinaryTreeNode(1);
            BinaryTreeNode n6 = new BinaryTreeNode(1);
            BinaryTreeNode n7 = new BinaryTreeNode(1);
    
            n1.left = n2;
            n2.left = n3;
            n3.left = n4;
            n4.left = n5;
    
    
            System.out.println(isBalanced(n1));
            System.out.println(isBalanced2(n1));
            System.out.println("----------------");
        }
    
        // 1
        //  \
        //   2
        //    \
        //     3
        //      \
        //       4
        //        \
        //         5
        private static void test5() {
            BinaryTreeNode n1 = new BinaryTreeNode(1);
            BinaryTreeNode n2 = new BinaryTreeNode(1);
            BinaryTreeNode n3 = new BinaryTreeNode(1);
            BinaryTreeNode n4 = new BinaryTreeNode(1);
            BinaryTreeNode n5 = new BinaryTreeNode(1);
            BinaryTreeNode n6 = new BinaryTreeNode(1);
            BinaryTreeNode n7 = new BinaryTreeNode(1);
    
            n1.right = n2;
            n2.right = n3;
            n3.right = n4;
            n4.right = n5;
    
    
            System.out.println(isBalanced(n1));
            System.out.println(isBalanced2(n1));
            System.out.println("----------------");
        }
    
        public static void main(String[] args) {
            test1();
            test2();
            test3();
    
            test4();
            test5();
        }
    
    
    }

=======

欢迎加入群聊：

![70][]

[70]: /images/20220505/f795a8ccd2ef441da49907f7017bf5d6.png