Friday, September 8, 2017

110. Balanced Binary Tree

https://leetcode.com/problems/balanced-binary-tree/description/
Solution: at each recursion step, check if left and right child are both balanced. At the same time check the maximum depth for each child.
    bool treeTrav(TreeNode* node, int& lev) {
        if(!node) return true;
        int levL = 0, levR = 0;
        if(treeTrav(node->left, levL) && treeTrav(node->right, levR))
            if(abs(levL-levR)>1) return false;
            else {
                lev = max(levL, levR) + 1;
                return true;
            }
        return false;
    }
    bool isBalanced(TreeNode* root) {
        int l = 0;
        return treeTrav(root, l);
    }

No comments:

Post a Comment