• Balanced Binary Tree

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. 题目翻译:
给定一颗二叉树， 写一个函数来检测这棵树是否是平衡二叉树. 对于这个问题, 一颗平衡树的定义是其中任意节点的左右子树的高度差不大于1. 解题思路:
这道题其实就是应用DFS，对于一颗二叉树边计算树的高度边计算差值，针对树里面的每一个节点计算它的左右子树的高度差，如果差值大于1，那么就返回-1，如果不大于1，从下往上再次检测. 时间复杂度:
由于是运用DFS，所以时间复杂度为O(n). 代码如下: 1. 2. / 3. * Definition for binary tree 4. * struct TreeNode { 5. * int val; 6. * TreeNode left; 7. * TreeNode right; 8. * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 9. * }; 10. / 11. class Solution { 12. public: 13. bool isBalanced(TreeNode root) { 14. //corner case check 15. if(root == NULL) 16. return true; 17. int isBalanced = getHeight(root); 18. if(isBalanced != -1) 19. return true; 20. else 21. return false; 22. } 23. 24. int getHeight(TreeNode* root) 25. { 26. if(root == NULL) 27. return 0; 28. int leftHeight = getHeight(root->left); 29. if(leftHeight == -1) 30. return -1; 31. int rightHeight = getHeight(root->right); 32. if(rightHeight == -1) 33. return -1; 34. int diffHeight = rightHeight > leftHeight? rightHeight-leftHeight:leftHeight-rightHeight; 35. if(diffHeight > 1) 36. return -1; 37. else 38. return diffHeight = (rightHeight>leftHeight?rightHeight:leftHeight)+1; 39. } 40. };