Binary Tree in Leetcode

Cousins in Binary Tree

The idea of this problem is to use the same thought on nodes in same level, but the difference is to check whether the node on same level has same parent. So the precondition is the unchecked 2 nodes they are in the same level, then could do the continue. The true condition is 2 nodes in same level, and have different parent node then could be confirmed as cousins node. I created a tuple to detect the parent of each node then after check in same level then check whether they have same parent according to the tuple created.

Invert Binary Tree

The idea of this problem is utilize a list to implement the binary Tree, but difference is to revert the order of left node and right node, so I provided 3 situations include all scenario: first is left and right both are not empty, second is first is empty and right is not, third is right is empty and left is not, I utilize a temp node to do the switch of both node; and borrow the level to check each same level; when the node are in same level, do the switch operation then go to the next level. When no more nodes after the last level(no matter single or double), jump out the loop.

Implement Prefix Trie

reference from: https://leetcode.com/articles/implement-trie-prefix-tree/ So according the article provided by Leetcode, the challenge is to solve the issue on find the prefix or find the whole word in the prefix tree. The idea is convert the word into a tree, and each character is a node, if 2 characters are close, then add the link between each other.

Based on the idea, it defines 2 functions one is insert, another is search, the only difference is whether the word searched is reaching the end of word. When insert the character into tree, it was easy to understand, iterate the whole word, if there is character then pass, if not create a new node; the value of node is the distance from ‘a’ in ASCii.

Maximum Width of Binary Tree

Reference:

https://gist.github.com/CodeMySky/9fc0317dde77d815ddfb39150a9c2fa0

It is the most simply solution which easy to understand i could find from Resource.

This is also a problem solve with level, after iterate one level, then update each level. Instead the original tree, convert the original tree to a new tree constructer with the number of node(like id), the encode is based on the location of node. Start from root is 1, left is 2, right is 3, so the left node is 2*curr.val, right node is 2*curr.val + 1.

So start from level with root only, and express each level using queue. Queue is FIFO, so the first element is the most left element of one level, so give default is lastelement = firstelement(with 1 node only), when iterate to the last one of level, update to the lastelement. For each level, we do the same operation.