[OJ.leetcode] balanced-binary-tree

https://oj.leetcode.com/problems/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.

/* solution: modified preorder (O(n)) 매 순회마다 left, right 의 depth를 비교해서 >1 이면 return false more than 1 이라고 했으므로 인터뷰어와 1 와 같은 예제도 balanced 인지 사전 논의 필요 / 2 1번에 accepted(tree, BST에 강한듯) */ /** * 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 isBalanced(TreeNode *root) { if(root == NULL) return true; int leftDepth = findDepth(root->left, 1); int rightDepth = findDepth(root->right, 1); if(leftDepth == -1 || rightDepth == -1 || abs(leftDepth-rightDepth) > 1) { return false; } return true; } int findDepth(TreeNode* node, int depth) { if(node == NULL) { return depth; } int leftDepth = findDepth(node->left, depth+1); int rightDepth = findDepth(node->right, depth+1); if(leftDepth == -1 || rightDepth == -1 || abs(leftDepth-rightDepth) > 1) { return -1; } return max(leftDepth, rightDepth); } };