LeetCode :: 1.Balanced Binary Tree [树类题目分析]

LeetCode :: 1.Balanced Binary Tree [树类题目分析]

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtreesof every node never differ by more than 1.

这道题目，我选为树类题目的第一题，难度比较低，AC率也高达30%+。虽然题目比较好AC，但是涉及的知识点还是值得回顾一下的。

其实这个红字定义就是AVL（平衡二叉查找树）的一个条件。这样构造的树，保证了树的深度是logN，现在这题目来判断一下这个条件是否成立。

一般树的题目很容易想到的就是递归了，因为树本身就是递归定义出来的，以二叉树为例，定义如下：二叉树是n(n>=0)个有限结点构成的集合。N=0称为空二叉树；n>0的二叉树由一个根结点和两互不相交的，分别称为左子树和右子树的二叉树构成。

解法一、这里最直接的想法是，既然需要每个节点的左右子树的高度差（绝对值）都小于等于1，那么先构建一个求高度的函数height，这里求高度的函数的遍历顺序是后序遍历，然后再从根节点开始，先序遍历（实验室的小伙伴说是后序，这里肯定是先序遍历，因为是先判断了根节点的左右子树高度差）判断每个节点。这样做效率不高，因为重复遍历了两次。

/*** Definition for binary tree* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:int height(TreeNode *node){if (!node)return 0;int  heiL = height(node -> left);int  heiR = height(node -> right);return 1 + (heiL > heiR ? heiL : heiR); }bool isBalanced(TreeNode *root) {if (root == NULL)return true;int diff = height(root -> left) - height(root -> right);if (diff > 1 || diff < -1)return false;return isBalanced(root -> left) && isBalanced(root -> right);}};

解法二、 为了避免两次遍历，直接第一次后序遍历，遍历的时候记录下深度，并且判断便可。

/*** Definition for binary tree* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:bool checkBalance(TreeNode *node, int &dep){if (node == NULL){dep = 0;return true;}int leftDep, rightDep;bool leftBalance = checkBalance(node->left, leftDep);bool rightBalance = checkBalance(node->right, rightDep);dep = max(leftDep, rightDep) + 1;return leftBalance && rightBalance && (abs(rightDep - leftDep) <= 1);}bool isBalanced(TreeNode *root) {// Start typing your C/C++ solution below// DO NOT write int main() functionint dep;return checkBalance(root, dep);}
};