Test Leetcode 104. Maximum Depth of Binary Tree-CodePudding

I am testing the leetcode 104 Maximum Depth of Binary Tree. While testing the case root = [3,9,20,None, None,15,7] . The output should be 3 but it shows 2. Could someone help me with this. Thanks

class TreeNode:
    def __init__(self,val=0, left=None, right=None):
        self.val = val
        self.left = left        
        self.right = right
    
def createTreeNode(nodeList):
    root = TreeNode(nodeList[0])
    root.left = TreeNode(nodeList[1])
    root.right = TreeNode(nodeList[2]) 
    return root        

def maxDepth(root):
    if root is None:
        return 0
    else:
        max_left = maxDepth(root.left)
        max_right = maxDepth(root.right)
        return max(max_left, max_right)   1

def main():    
    ListNode1 = [3,9,20,None,None,15,7]
    TreeNode1 = createTreeNode(ListNode1)
    print (maxDepth(TreeNode1))
main()

CodePudding user response：

You do not construct your tree in the right way. Leetcode recently added an option to visualize trees (see Tree Visualizer in the right-bottom corner of the Testcase tab). For your input:

In test cases usually trees are represented as in-order traversal, so you can build up a tree from it using suitable traversal algorithm or you could build it manually:

root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.right = TreeNode(7)
root.right.left = TreeNode(15)

Your algorithm is correct, but I would refactor it a bit:

def maxDepth(root):
    if not root:
        return 0
    max_left = maxDepth(root.left)
    max_right = maxDepth(root.right)
    return max(max_left, max_right)   1