【剑指offer】面试题55（2）：平衡二叉树

超、凢脫俗 2022-06-11 07:08 151阅读 0赞

## 题目 ##

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。  
如果某二叉树中的任意节点的左、右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

## 思路 ##

我们用**后序遍历**的方式遍历二叉树的每个节点，那么在遍历到一个节点之前我们就已经遍历了它的左、右子树。  
只要在遍历每个节点的时候记录它的深度，我们就可以一边遍历一边判断每个节点是不是平衡的。

ps：根节点为null时是平衡二叉树

## 代码 ##

/**
     * 题目：
     * 输入一棵二叉树的根节点，判断该树是不是平衡二叉树。
     * 如果某二叉树中的任意节点的左、右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
     * 
     * ps：根节点为null时返回true
     * 
     * @author peige
     */
    public class _55_02_BalancedBinaryTree {
        
    
        public static class TreeNode {
        
            public int val = 0;
            public TreeNode left = null;
            public TreeNode right = null;
            public TreeNode(int val) {
                this.val = val;
            }
        }
    
        public boolean IsBalanced_Solution(TreeNode root) {
            if(root == null)
                return true;
            int res = treeDepth(root);
            if(res == -1)
                return false;
            return true;
        }
    
        /**
         * 一旦出现不平衡的节点，开始递归返回-1 
         */
        public int treeDepth(TreeNode root) {
            if(root == null)
                return 0;
            int leftDepth = treeDepth(root.left);
            if(leftDepth == -1)
                return -1;
            int rightDepth = treeDepth(root.right);
            if(rightDepth == -1)
                return -1;
            // 该节点是否平衡
            if(leftDepth - rightDepth > 1 || leftDepth - rightDepth < -1)
                return -1;
            // 加上根节点的长度（后序遍历）
            return leftDepth > rightDepth ? leftDepth + 1: rightDepth + 1;
        }
    }

## 测试 ##

public class _55_02_Test {
        
    
        public static void main(String[] args) {
            test1();
            test2();
            test3();
            test4();
        }
    
        /**
         * 功能测试
         * 树1：
         *         1
         *       /   \
         *      2     3
         *     / \   / \
         *    4   5 6   7
         *   /
         *  8 
         *  
         * 树2：
         *         1
         *       /   \
         *      2     3
         *     / \   / \
         *    4   5 6   7
         *   /   / \
         *  8   9  10
         *       \
         *       11
         *  
         */
        private static void test1() {
            TreeNode node1 = new TreeNode(1);
            TreeNode node2 = new TreeNode(2);
            TreeNode node3 = new TreeNode(3);
            TreeNode node4 = new TreeNode(4);
            TreeNode node5 = new TreeNode(5);
            TreeNode node6 = new TreeNode(6);
            TreeNode node7 = new TreeNode(7);
            TreeNode node8 = new TreeNode(8);
    
            node1.left = node2;
            node1.right = node3;
            node2.left = node4;
            node2.right = node5;
            node3.left = node6;
            node3.right = node7;
            node4.left = node8;
    
            boolean b = new _55_02_BalancedBinaryTree().IsBalanced_Solution(node1);
            MyTest.equal(b, true);
    
            TreeNode node9 = new TreeNode(9);
            TreeNode node10 = new TreeNode(10);
            TreeNode node11 = new TreeNode(11);
            node5.left = node9;
            node5.right = node10;
            node9.right = node11;
    
            b = new _55_02_BalancedBinaryTree().IsBalanced_Solution(node1);
            MyTest.equal(b, false);
        }
    
        private static void test2() {
            TreeNode node1 = new TreeNode(1);
            _55_02_BalancedBinaryTree bbt = new _55_02_BalancedBinaryTree();
            boolean b = bbt.IsBalanced_Solution(node1);
            MyTest.equal(b, true);
        }
    
        private static void test3() {
            _55_02_BalancedBinaryTree bbt = new _55_02_BalancedBinaryTree();
            boolean b = bbt.IsBalanced_Solution(null);
            MyTest.equal(b, false);
        }
    
        /**
         * 提交的时候没过的case：
         *             1
         *            /
         *           2  
         *          /
         *         3
         *        /
         *       4
         *      /
         *     5     
         */
        private static void test4() {
            TreeNode node1 = new TreeNode(1);
            TreeNode node2 = new TreeNode(2);
            TreeNode node3 = new TreeNode(3);
            TreeNode node4 = new TreeNode(4);
            TreeNode node5 = new TreeNode(5);
            node1.left = node2;
            node2.left = node3;
            node3.left = node4;
            node4.left = node5;
    
            _55_02_BalancedBinaryTree bbt = new _55_02_BalancedBinaryTree();
            boolean b =bbt.IsBalanced_Solution(node1);
            MyTest.equal(b, false);
        }
    }