leetcode110

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private int height(TreeNode node)
        {
            if (node == null)
            {
                return 0;
            }
            int lH = height(node.left);
            if (lH == -1)
            {
                return -1;
            }
            int rH = height(node.right);
            if (rH == -1)
            {
                return -1;
            }
            if (lH - rH < -1 || lH - rH > 1)
            {
                return -1;
            }
            return Math.Max(lH, rH) + 1;
        }

        public bool IsBalanced(TreeNode root)
        {
            if (root == null)
            {
                return true;
            }
            return height(root) != -1;

        }
}      

https://leetcode.com/problems/balanced-binary-tree/#/description

補充一個python的實作：

1 class Solution:
 2     def __init__(self):
 3         self.result = True
 4         
 5     def maxDepth(self,root):
 6         if root == None:
 7             return 0
 8         l = self.maxDepth(root.left)
 9         r = self.maxDepth(root.right)
10         d = max(l,r) + 1
11         if abs(l - r) > 1:
12             self.result = False
13         return d
14     
15     def isBalanced(self, root: TreeNode) -> bool:
16         self.maxDepth(root)
17         return self.result      

轉載于:https://www.cnblogs.com/asenyang/p/6745121.html