剑指offer | 55 - II. 平衡二叉树

我就是我 2022-12-28 00:55 81阅读 0赞

**题目**

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

**示例 1:**

给定二叉树 [3,9,20,null,null,15,7]
    
        3
       / \
      9  20
        /  \
       15   7
    
    返回 true 。

**示例 2:**

给定二叉树 [1,2,2,3,3,null,null,4,4]
    
           1
          / \
         2   2
        / \
       3   3
      / \
     4   4
    
    返回 false 。

**限制：**

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

--------------------

**方法1：** 先序遍历，每次都递归求当前子树的深度，然后求左右子树高度差，但这种方法会重复计算。

*  时间复杂度： O ( N l o g N ) O(NlogN) O(NlogN)
 *  空间复杂度： O ( N ) O(N) O(N)

class Solution { 
    public:
    	bool isBalanced(TreeNode* root) { 
    		if (root == NULL) return true;//如果该子树为空，则一定是平衡的（因为没有左右子树）
    		if (abs(getHeight(root->left) - getHeight(root->right)) > 1) return false;
    		return isBalanced(root->left)&& isBalanced(root->right);
    	}
    	int getHeight(TreeNode* root)
    	{ 
    		if (root == NULL) return 0;
    		int leftHeight = getHeight(root->left);
    		int rightHeight = getHeight(root->right);
    		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    	}
    };

**方法二：** 后序遍历+剪枝

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

/*后序遍历解题*/
    /* 使用后序遍历的方式遍历二叉树的每个节点，那么在遍历到一个节点之前我们就已经 遍历了它的左右子树。只要在每个节点的时候记录它的深度(某一节点的深度等于它到叶节点的路径的长度） 就可以判断每个节点是不是平衡的 */
    /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
    class Solution { 
    public:
        bool isBalanced(TreeNode* root) { 
            return depth(root) != -1;
        }
        int depth(TreeNode* root){ 
            if(!root) return 0;
            int left = depth(root->left);
            if (left == -1) return -1;
            int right = depth(root->right);
            if (right == -1) return -1;
            return  abs(left - right) < 2 ? max(left, right) + 1 : -1;
        }
    };