剑指 Offer 55 - II. 平衡二叉树

喜欢ヅ旅行 2022-12-19 08:39 147阅读 0赞

# 题目 #

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

示例 1:  
给定二叉树 \[3,9,20,null,null,15,7\]  
![在这里插入图片描述][20201106100649924.png_pic_center]  
返回 true 。

示例 2:  
给定二叉树 \[1,2,2,3,3,null,null,4,4\]  
![在这里插入图片描述][20201106100705715.png_pic_center]  
返回 false 。

限制：

*  1 <= 树的结点个数 <= 10000

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof][https_leetcode-cn.com_problems_ping-heng-er-cha-shu-lcof]

# 解题思路 #

两种思路

思路一:

*  后序遍历
 *  计算当前节点的高度
    
     *  当前节点为null,直接返回高度0
     *  计算当前节点左子树高度,如果不是平衡树,提前返回
     *  计算当前节点右子树的高度,如果不是平衡树,提前返回
     *  计算当前节点树的高度,如果是平衡树,返回1 + 左子树高度和右子树高度的最大值,不是平衡树,返回-1

思路二:

*  也是后序遍历的思想
 *  判断当前节点是否为null,为null则直接返回
 *  递归判断当前节点的左子树是否为平衡树
 *  递归判断当前节点的右子树是否为平衡树
 *  判断当前树是否为平衡树

# 代码 #

思路一:

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    class Solution { 
        public boolean isBalanced(TreeNode root) { 
            return height(root) != -1;
        }
    
        private int height(TreeNode node) { 
            if (node == null) { 
                return 0;
            }
    		
    		// 计算左子树高度
            int leftHeight = height(node.left);
            if (leftHeight == -1) { 
                return -1;
            }
    
    		// 计算右子树高度
            int rightHeight = height(node.right);
            if (rightHeight == -1) { 
                return -1;
            }
    
    		// 计算当前树高度,不是平衡树直接返回-1
            return Math.abs(leftHeight - rightHeight) <= 1 ? 1 + Math.max(leftHeight, rightHeight) : -1;
        }
    }

*  时间复杂度 O(n): n为树的节点数；最差情况下，需要递归遍历树的所有节点。
 *  空间复杂度 O(n): 最差情况下（树退化为链表时），系统递归需要使用 O(n) 的栈空间。

思路二:

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    class Solution { 
        public boolean isBalanced(TreeNode root) { 
        	// 递归结束条件
            if (root == null) { 
                return true;
            }
    		
    		// 判断左子树,右子树,当前节点
            return isBalanced(root.left) && isBalanced(root.right) && Math.abs(height(root.left) - height(root.right)) <= 1;
        }
    
        private int height(TreeNode node) { 
        	// 计算树的高度
            if (node == null) { 
                return 0;
            }
    		
            return 1 + Math.max(height(node.left), height(node.right));
        }
    }

*  时间复杂度:O(nlogn),满二叉树情况下遍历所有节点
 *  空间复杂度:O(n),极端情况下,树退化成为链表,递归使用O(n)的栈空间

[20201106100649924.png_pic_center]: /images/20221120/27f94e08ca0a45cd9bec5ad69fd8ddad.png
[20201106100705715.png_pic_center]: https://img-blog.csdnimg.cn/20201106100705715.png#pic_center
[https_leetcode-cn.com_problems_ping-heng-er-cha-shu-lcof]: https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof