【LeetCode】110. Balanced binary tree (2 brushes of wrong questions)

• Ideas
  That is, the height difference between the left and right subtrees is not higher than 1 that will do , It needs to be seen from the bottom up , So we use the method of post order traversal , Use post order traversal recursion , Then calculate the height difference between the left and right subtrees , If not, return directly false, If you are satisfied at the top, you will return true.
  Recursive Trilogy
  Recursive parameters and return values ： The parameter is the current node , The return value is the height difference between the left and right subtrees of the current node ;
  The termination condition of recursion ： Return when empty true, When the height difference between the left and right subtrees is greater than 1 When to return to false;
  Recursive single-layer logic ： Use post order traversal , Then it is the traversal order in left and right , Enter the next floor left and right , And return .
• problem
  There is a problem in the middle of this inscription , That is, the returned value does not know which one to return , If not, return -1, Then who is satisfied to return ？
  So I refer to the solution , Find that the thought is correct , This is actually the height , It needs to be followed from bottom to top , If it's depth , From top to bottom is the preface , Then for meeting the conditions , Returns the larger height in the left and right subtrees +1.
  

/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */

func max(a, b int) int {
    
    if a >= b {
    
        return a
    }
    return b
}

func height(root *TreeNode) int {
    
    if root == nil {
    
        return 0
    }
    //  Left 
    leftHeight := height(root.Left)
    if leftHeight == -1 {
    
        return -1
    }
    //  Right 
    rightHeight := height(root.Right)
    if rightHeight == -1 {
    
        return -1
    }
    //  in 
    var res int
    if leftHeight - rightHeight > 1 || rightHeight - leftHeight > 1 {
    
        res = -1
    } else {
    
        res = 1 + max(leftHeight, rightHeight)
    }
    return res
}

func isBalanced(root *TreeNode) bool {
    
    if root == nil {
    
        return true
    }
    if height(root) == -1 {
    
        return false
    }
    return true
}