[LeetCode][python3]Day11. Diameter of Binary Tree (30-Day LeetCoding Challenge)

30 days! Lets go Lets go!
N2I -2020.04.11

1. A recursive Solution

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.number_of_nodes = 1
        def depth(node):
            if not node: return 0
            L = depth(node.left)
            R = depth(node.right)
            # path
            self.number_of_nodes = max(self.number_of_nodes, L+R+1)
            return max(L, R) + 1
        
        depth(root)
        return self.number_of_nodes - 1

Explanation:

This solution using recursive way to solve the problem. A longest path in every situations, there must be one node and only that node in the path which its parent node is not in the path (see the pic below, node 2 is that node). And the longest path will be the left.length+right.length in that node.

The recursive function will return the max length from child node to the parent node, which is chose between left child or right child. In the pic below, you’ll see the red number is the return value from child node. The yellow is the chosen length and was added by one and return by its parent to the parent’s parent. The blue part is the max path. Compare every max path in each node and fine the max one: 2+3=5 in node 2.

2. My Solution

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:        
        if root==None:
            return 0
        stack=[]
        stack.append([root,-1,-1,0])
        tmp=(-1,1)
        maxlen=0
        while stack:
            state=stack.pop()
            if state[0]==None:
                tmp=(0,state[3])
                continue  
            state[tmp[1]]=tmp[0]
            #print(state[0].val,state[1:],tmp)
            tmp=(-1,1)
            if state[1]==-1:
                stack.append(state)
                stack.append([state[0].left,-1,-1,1])
                continue
            elif state[2]==-1:
                stack.append(state)
                stack.append([state[0].right,-1,-1,2])
                continue
            else:
                maxlen=max(maxlen,state[1]+state[2])
                tmp=(max(state[1],state[2])+1,state[3])
        return maxlen

I’m trying to use a stack instead of recursive. A stack use to be faster than recursive, but it seems I didn’t wrote it well.