首页 > 代码库 > LeetCode: Balanced Binary Tree

LeetCode: Balanced Binary Tree

LeetCode: 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 subtrees of every node never differ by more than 1.

地址:https://oj.leetcode.com/problems/balanced-binary-tree/

算法:递归解决,并且在递归的过程中求出树的深度。代码:

 1 /** 2  * Definition for binary tree 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11 public:12     bool isBalanced(TreeNode *root) {13         if(!root){14             return true;15         }16         int depth = 0;17         return subIsBalanced(root,depth);18     }19     bool subIsBalanced(TreeNode *root, int &depth){20         if(!root){21             depth = 0;22             return true;23         }24         int left_depth;25         bool left = subIsBalanced(root->left,left_depth);26         int right_depth;27         bool right = subIsBalanced(root->right,right_depth);28         depth = left_depth > right_depth ? left_depth + 1 : right_depth + 1;29         if(left && right){30             if(left_depth > right_depth + 1 || right_depth > left_depth + 1){31                 return false;32             }33             return true;34         }35         return false;36     }37 };

 

LeetCode: Balanced Binary Tree