[LeetCode] 1022. Sum of Root To Leaf Binary Numbers

 Problem : https://leetcode.com/problems/sum-of-root-to-leaf-binary-numbers/

Use DFS to get the result.

Time complexity = O(N)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int sumRootToLeaf(TreeNode root) {
        // dfs
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        
        stack1.push(root);
        stack2.push(0);
        
        int result = 0;
        
        while(!stack1.isEmpty()) {
            TreeNode node = stack1.pop();
            int tmp = stack2.pop();
            
            tmp = (tmp << 1) | node.val;
            if (node.left == null && node.right == null) {
                result += tmp;
            }
            
            if (node.right != null) {
                stack1.push(node.right);
                stack2.push(tmp);
            }
            
            if (node.left != null) {
                stack1.push(node.left);
                stack2.push(tmp);
            }
        }
        
        return result;
    }
}

[LeetCode] 1026. Maximum Difference Between Bode and Ancestor

 Problem : https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/

Calculate the difference of node.val and the maximum and minimum value from its child trees.

Time complexity = O(N), N = total nodes of the given tree.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxAncestorDiff(TreeNode root) {
        return postOrder(root)[2];
    }
    
    int[] postOrder(TreeNode node) {
        int mi = node.val;
        int mx = node.val;
        int diff = 0;
        
        for (TreeNode child: new TreeNode[] {node.left, node.right}) {
            if (child != null) {
                // mi, mx, diff
                int[] tmp = postOrder(child);
                
                mi = Math.min(mi, tmp[0]);
                mx = Math.max(mx, tmp[1]);
                
                diff = Math.max(diff, tmp[2]); 
                diff = Math.max(diff, Math.abs(node.val - tmp[0]));
                diff = Math.max(diff, Math.abs(node.val - tmp[1])); 
            }
        }
        
        return new int[] {mi, mx, diff};
    }
}

[LeetCode] 404. Sum of Left Leaves

 Problem : https://leetcode.com/problems/sum-of-left-leaves/

Use post-order traversal to accumulate left leave values.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        
        self.result = 0
        
        def postorder(node):
            if not node.left and not node.right:
                # find a leaf
                return True
            
            if node.left and postorder(node.left):
                # find a left leaf
                self.result += node.left.val
            
            if node.right:
                postorder(node.right)
            
            return False
        
        postorder(root)
        return self.result

[LeetCode] 428. Serialize and Deserialize N-ary Tree

 Problem: https://leetcode.com/problems/serialize-and-deserialize-n-ary-tree/

Use preorder traversal to dump the given tree. To make the deserialize process simpler, we dump the size of children list after the node value to indicate how many children node is needed under current node.

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Codec:
    def serialize(self, root: 'Node') -> str:
        """Encodes a tree to a single string.
        
        :type root: Node
        :rtype: str
        """
        
        def preorder(node):
            yield str(node.val)
            yield str(len(node.children))
            
            for nxt in node.children:
                yield from preorder(nxt)
            
        return ','.join(preorder(root)) if root else ''
	
    def deserialize(self, data: str) -> 'Node':
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: Node
        """
        
        data = data.split(',') if data else []
        

        def helper(index):
            if index >= len(data):
                return None, index
            
            node = Node(val=int(data[index]), children=[])
            index += 1
            size = int(data[index])
            index += 1
            
            for _ in range(size):
                child, index = helper(index)
                node.children.append(child)
                
            return node, index
                
        return helper(0)[0]

# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

[LeetCode] 1161. Maximum Level Sum of a Binary Tree

 Problem : https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/

This is an easy problem which can be solved by either DFS or BFS.

But it needs to be aware that because node may have negative value, we cannot determine the final sum of a level until traversal is completed. 

Time Complexity = O (N + N)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxLevelSum(self, root: Optional[TreeNode]) -> int:
        levels = []
        stack = [(root, 0)]
        
        while stack:
            node, index = stack.pop()
            
            if index == len(levels):
                levels.append(node.val)
            else:
                levels[index] += node.val
 
            if node.right:
                stack.append((node.right, index + 1))
            if node.left:
                stack.append((node.left, index + 1))
        
        mxSoFar = levels[0]
        miLevel = 0
        
        for level, sums in enumerate(levels):
            if sums > mxSoFar:
                mxSoFar = sums
                miLevel = level
        
        return miLevel + 1

[LeetCode] 742. Closest Leaf in a Binary Tree

 Problem : https://leetcode.com/problems/closest-leaf-in-a-binary-tree/

Because the goal is to find the nearest leaf node,  we use postorder to keep the shortest path to a leaf in left sub-tree or right sub-tree. 

If current node's value == k,  we use the shorter path from left or right sub-tree as the potential result. 

If k does not exist in either left sub-tree or right sub-tree, we only keep the shorter path

If k exists in left sub-tree, we consider path-to-value-k-in-left-sub-tree + shortest-path-to-leaf-in-right-sub-tree as potential result.

Similar procedure when k exists in right sub-tree.

This problem cannot solve by preorder traversal, because it cannot locate the lowest common ancestor with preorder traversal. 

Lesson learned:

- Postorder is useful we need to build path from leaf. 

- On each node, we can build a path by connecting path from left tree and path from right tree.

- We can return as much info as we need in postorder traversal.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:
        self.result = None
        
        def postorder(node):
            if not node.left and not node.right:
                if node.val == k:
                    self.result = (0, k)
                    
                return (1, node.val == k, node.val)
            
            leftDepth, leftHasK, leftLeaf = postorder(node.left) if node.left else (1000, False, -1)
            rightDepth, rightHasK, rightLeaf = postorder(node.right) if node.right else (1000, False, -1)
            
            
            if node.val == k:
                if leftDepth < rightDepth:
                    self.result = (leftDepth, leftLeaf)
                    return (1, True, -1)
                else:
                    self.result = (rightDepth, rightLeaf)
                    return (1, True, -1)
            elif leftHasK:
                if leftDepth + rightDepth < self.result[0]:
                    self.result = ((leftDepth + rightDepth), rightLeaf)

                return (leftDepth+1, True, -1)
            elif rightHasK:
                if rightDepth + leftDepth < self.result[0]:
                    self.result = ((rightDepth + leftDepth), leftLeaf)

                return (rightDepth+1, True, -1)
            else:
                if leftDepth < rightDepth:
                    return (leftDepth+1, False, leftLeaf)

                return (rightDepth+1, False, rightLeaf)
            
        
        postorder(root)
        
        return self.result[1]

[LeetCode] 652. Find Duplicate Subtrees

 Problem : https://leetcode.com/problems/find-duplicate-subtrees/

A tree can be represented by its path. 2 trees are identical if their dumped paths are the same.

Use postorder traversal to find sub-trees with same dumped path.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
        
        seen = defaultdict(list)
        result = []
        
        def postorder(node):
            if not node: return "#"
            
            key = '(' + str(node.val) + ')'+ postorder(node.left) + postorder(node.right)
            seen[key].append(node)
            
            if len(seen[key]) == 2:
                result.append(node)
            
            return key
        
        postorder(root)
        
        return result

[LeetCode] 1448. Count Good Nodes in Binary Tree

 Problem : https://leetcode.com/problems/count-good-nodes-in-binary-tree/

Use DFS to find number of nodes where value not less than the current local maximum value.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        
        result = 0
        stack = [(root, -10**4)]
        
        while stack:
            node, mx = stack.pop()
            
            if mx <= node.val:
                result += 1
                mx = node.val
            
            if node.right:
                stack.append((node.right, mx))
            
            if node.left:
                stack.append((node.left, mx))
        
        return result

[LeetCode] 549. Binary Tree Longest Consecutive Sequence II

 Problem : https://leetcode.com/problems/binary-tree-longest-consecutive-sequence-ii/

Assume we only construct increasing consecutive sequence. So a new node value can append to a sequence in below 3 scenarios:

[new value] xxxxx : add to the start position

xxxxx [new value] : add to the end position

xxxxx [new value] xxxxx : add to the middle of sequence from the left and right subtree.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def longestConsecutive(self, root: TreeNode) -> int:
        self.result = 0
        
        def postorder(node):
            """
            return (s, e)
            s : the length of the longest sequence which starts with 'node'
            e : the length of the longest sequence which ends by 'node'
            """
            
            if node.left and node.right:
                ls, le = postorder(node.left)
                rs, re = postorder(node.right)
                s = e = 1
                
                if node.left.val + 1 == node.val and node.val + 1 == node.right.val:
                    self.result = max(self.result, le + 1 + rs)
                    
                    s = max(s, rs + 1)
                    e = max(e, le + 1)
                
                if node.left.val - 1 == node.val and node.val - 1 == node.right.val:
                    self.result = max(self.result, ls + 1 + re)
                    
                    s = max(s, ls + 1)
                    e = max(e, re + 1)
                
                if node.left.val + 1 == node.val:
                    self.result = max(self.result, le + 1)
                    e = max(e, le + 1)
                
                if node.left.val - 1 == node.val:
                    self.result = max(self.result, ls + 1)
                    s = max(s, ls + 1)
                
                if node.right.val + 1 == node.val:
                    self.result = max(self.result, re + 1)
                    e = max(e, re + 1)
                
                if node.right.val - 1 == node.val:
                    self.result = max(self.result, rs + 1)
                    s = max(s, rs + 1)
            
                return s, e
            
            if node.left:
                ls, le = postorder(node.left)
                s = e = 1
                
                if node.left.val + 1 == node.val:
                    self.result = max(self.result, le + 1)
                    e = max(e, le + 1)
                
                if node.left.val - 1 == node.val:
                    self.result = max(self.result, ls + 1)
                    s = max(s, ls + 1)
                
                return s, e
            
            if node.right:
                rs, re = postorder(node.right)
                s = e = 1
                
                if node.right.val + 1 == node.val:
                    self.result = max(self.result, re + 1)
                    e = max(e, re + 1)
                
                if node.right.val - 1 == node.val:
                    self.result = max(self.result, rs + 1)
                    s = max(s, rs + 1)
                    
                return s, e
            
            self.result = max(self.result, 1)
            return 1, 1
        
        
        postorder(root)
        
        return self.result

[LeetCode] 814. Binary Tree Pruning

 Problem : https://leetcode.com/problems/binary-tree-pruning/

Use postorder traversal to check if sub-tree has "one".  Delete the sub-tree if it does not have "one".

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pruneTree(self, root: TreeNode) -> TreeNode:

        def postOrder(node):
            if not node:
                return False
            
            hasOneLeft = postOrder(node.left)
            if not hasOneLeft:
                node.left = None
            
            hasOneRight = postOrder(node.right)
            if not hasOneRight:
                node.right = None
            
            return node.val == 1 or hasOneLeft or hasOneRight
        
        return root if postOrder(root) else None

[LeetCode] 156. Binary Tree Upside Down

 Problem : https://leetcode.com/problems/binary-tree-upside-down/

Although it says every node has either 0 or 2 children in the given example. The input tree may only has left sub-tree.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def upsideDownBinaryTree(self, root: TreeNode) -> TreeNode:
        
        def helper(node):
            if node and node.left:
                lt = node.left
                node.left = None
                lt = helper(lt)
                
                rt = node.right
                node.right = None
                rt = helper(rt)
                   
                np = lt
                while np.right:
                    np = np.right
                
                np.left = rt
                np.right = node
                   
                return lt
                
            else:
                return node
            
        
        return helper(root)

[LeetCode] 331. Verify Preorder Serialization of a Binary Tree

 Problem : https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/

Re-create node list by splitting the input string with comma.

Then iterate the node list with pre-order traversal process.

Validate the tree node during traversal.

class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        nodes = preorder.split(',')
        
        if not nodes : return True
        
        def helper(i):
            if i >= len(nodes):
                return (i, False)
            
            if nodes[i] == '#':
                return (i, True)
            
            i, result = helper(i+1)
            if not result:
                return (i, False)
            
            i, result = helper(i+1)
            if not result:
                return (i, False)
            
            return (i, True)
        
        i, result = helper(0)
        
        return i == len(nodes) - 1 and result

[LeetCode] 257. Binary Tree Paths

Problem : https://leetcode.com/problems/binary-tree-paths/

DFS approach

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        
        def dfs(node):
            if node:
                suffix = []
                
                if node.left:
                    suffix += dfs(node.left)
                    
                if node.right:
                    suffix += dfs(node.right)
                
                return [[str(node.val)] + s for s in suffix] if suffix else [[str(node.val)]]
                
        
        return ['->'.join(path) for path in dfs(root)]

Iterative DFS approach

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        # dfs
        stack = [(root, [root.val])]
        result = []
        
        while stack:
            node, path = stack.pop()
            
            if not node.left and not node.right:
                result.append('->'.join(map(str, path)))
            else:
                if node.right:
                    stack.append((node.right, path + [node.right.val]))
            
                if node.left:
                    stack.append((node.left, path + [node.left.val]))
                
        return result

BFS approach

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        queue = deque([[root]]) if root else deque()
        result = []
        
        while queue:
            path = queue.popleft()
            
            if path[-1].left:
                queue.append(path + [path[-1].left])
            if path[-1].right:
                queue.append(path + [path[-1].right])
            
            if not path[-1].left and not path[-1].right:
                result.append(path)
        
        return map(lambda p: '->'.join(p), map(lambda path: map(lambda n: str(n.val), path), result))

Edited on 04/22/2021. Refactor DFS solution by appending suffix collected from lower level.

Edited on 06/06/2021. Add iterative DFS solution.

[LeetCode] 236. Lowest Common Ancestor of a Binary Tree

Problem: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

Search p, q in binary tree.  If both p and q are in the left sub-tree, the lowest common ancestor is in the left sub-tree. If both p and q are in the right sub-tree, the lowest common ancestor is in the right sub-tree. otherwise the current node is the lowest common ancestor.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        
        def postorder(node):
            if not node:
                return False, None
            
            leftFound, leftAncestor = postorder(node.left)
            if leftAncestor:
                return True, leftAncestor
            
            rightFound, rightAncestor = postorder(node.right)
            if rightAncestor:
                return True, rightAncestor
            
            if (leftFound or rightFound) and node in [p, q] :
                return True, node
            
            if leftFound and rightFound:
                return True, node
            
            return rightFound or leftFound or node in [p, q], None
        
        return postorder(root)[1]

Edited on 06/30/2021. Use postorder traversal to locate node p and q.

Edited on 11/07/2021. Simplify the postorder based solution. Because all node.val is unique, the order to find p or q does not matter.

[LeetCode] 226. Invert Binary Tree

Problem : https://leetcode.com/problems/invert-binary-tree/

Invert the tree recursively.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        return root != null ? 
                new TreeNode(root.val, invertTree(root.right), invertTree(root.left))
                : null;
    }
}

Updated on 02/17/2023. Replaced with a Java solution.

[LeetCode] 222. Count Complete Tree Nodes

 Problem : https://leetcode.com/problems/count-complete-tree-nodes/

DFS Solution:

Time Complexity = O ( N )

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def countNodes(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        return 1 + self.countNodes(root.left) + self.countNodes(root.right)
        

BFS Solution:

Time Complexity = O ( N )

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def countNodes(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        queue = deque([root])
        
        level = 0
        result = 0
        
        while queue:
            tmp = deque()
            result += len(queue)
            while queue:
                node = queue.popleft()
                if node.left:
                    tmp.append(node.left)
                if node.right:
                    tmp.append(node.right)
            
            # stop traversal when reach the last level  
            if len(tmp) < 2 ** level:
                return result + len(tmp)
            
            queue = tmp
        return result

[LeetCode] 173. Binary Search Tree Iterator

Problem : https://leetcode.com/problems/binary-search-tree-iterator/

Because in-order traverse BST can generate a ascending sequence.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class BSTIterator:

    def __init__(self, root: TreeNode):
        
        def inorder(node):
            if node:
                yield from inorder(node.right)
                yield node.val
                yield from inorder(node.left)
        
        self.nodes = list(inorder(root))

    def next(self) -> int:
        return self.nodes.pop()

    def hasNext(self) -> bool:
        return self.nodes


# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()

A stack based iterative solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class BSTIterator:

    def __init__(self, root: TreeNode):
        self.stack = [root] if root else []
        

    def next(self) -> int:
        node = self.stack[-1]
        
        while node.left:
            self.stack.append(node.left)
            tmp = node.left
            node.left = None
            node = tmp
        
        # pop the parent node
        self.stack.pop()
        
        if node.right:
            self.stack.append(node.right)
            node.right = None
        
        return node.val
        

    def hasNext(self) -> bool:
        return self.stack
        


# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()

Edited on 04/22/2021. Refactor the recursive and iterative solution.

[LeetCode] 145. Binary Tree Postorder Traversal

Problem : https://leetcode.com/problems/binary-tree-postorder-traversal/

Recursive solution:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        
        def postorder(node):
            if node:
                yield from postorder(node.left)
                yield from postorder(node.right)
                yield node.val
        
        return list(postorder(root))

Iterative solution:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        result = []
        stack = [root] if root else []
        
        while stack:
            node = stack[-1]
            
            if not node.left and not node.right:
                result.append(node.val)
                stack.pop()
            else:
                if node.right:
                    stack.append(node.right)
                    node.right = None

                if node.left:
                    stack.append(node.left)
                    node.left = None

        return result

Edited on 04/20/2021. Add the recursive approach.

Edited on 04/20/2021. Update the stack based iterative approach.

[LeetCode] 144. Binary Tree Preorder Traversal

Problem : https://leetcode.com/problems/binary-tree-preorder-traversal/

Recursive solution:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        def preorder(node):
            if node:
                yield node.val
                yield from preorder(node.left)
                yield from preorder(node.right)

        return list(preorder(root))

Iterative solution:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        result = []
        stack = [root] if root else []
        
        while stack:
            node = stack.pop()
            
            result.append(node.val)
            
            for child in filter(None, [node.right, node.left]):
                stack.append(child)
        
        return result

Edited on 04/20/2021. Update iterative solution. Same approach can apply to N-array tree too.

Edited on 04/20/2021. Update recursive solution. Use 'yield' and 'yield from'.

[LeetCode] 124. Binary Tree Maximum Path Sum

Problem : https://leetcode.com/problems/binary-tree-maximum-path-sum/

On each node,  its path sum = Max( node,  node + left_path, node  + right_path, node + left_path + right_path)

Use postorder traversal to find the maximum path sum

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        self.result = -1000
        
        def postOrder(node):
            
            if node.left and node.right:
                left = postOrder(node.left)
                right = postOrder(node.right)
                
                self.result = max(self.result, node.val + left + right, node.val + left, node.val + right, node.val)
                
                return max(node.val + left, node.val + right, node.val)
            
            if node.left:
                left = postOrder(node.left)
                
                self.result = max(self.result, node.val + left, node.val)
                
                return max(node.val + left, node.val)
            
            if node.right:
                right = postOrder(node.right)
                
                self.result = max(self.result, node.val + right, node.val)
                return  max(node.val + right, node.val)
            
            self.result = max(self.result, node.val)
            return node.val
        
        if root:
            postOrder(root)
        
        
        return self.result