Lowest Common Ancestor in a Binary Tree

You are given the root of a binary tree whose node values are all distinct, and two values a and b that both occur in the tree.

The lowest common ancestor of two nodes is the deepest node that has both of them as descendants, where a node counts as a descendant of itself.

The tree from the examples with a = 6 and b = 4: the lowest common ancestor is 5.

Return the value of the lowest common ancestor of the nodes holding a and b.

Tree Encoding

Your function receives root as a TreeNode. The node type is provided for you, with val, left, and right fields.

The examples below write the tree as its level-order traversal, where null marks a missing child of a listed node and trailing nulls are omitted. That is only how the input is displayed; the decoding is done for you.