Judge if the leaves of a tree are in the same level or not:
1. Iteration Version:
If the tree is null,return true. ?
Else,using the level order traversal to examine every levels of the tree and judge according to wheather all the leaves are at the same level.
Algoritm: SameLevel(node* root)
Input:a pointer of node pointing to a root of a tree.
Output:a bool which is true when all the leaves(if exsits) are at the same level and false vice versa.
queue<int> tem;
if root == NULL then
return true;
tem.push(root);
while tem.size() != 0 do
flag <- -1; //-1 for uninitialized,0 for non-leaf nodes before,1 for leaves before
size <- tem.size(); //record the node number of this level
for i <- 0 to i < size do
NodeTem <- tem.front();
tem.pop();
if NodeTem.leftc == NULL && Node.right == NULL then
if flag == -1 then
flag <- 1;
else if flag == 0 then
return false;
else
if flag == -1 then
flag <- 0;
else if flag == 1 then
return false;
//push the next level into the queue
if nodeTem.leftc != NULL then
tem.push(nodeTem.leftc);
if nodeTem.rightc != NULL then
tem.push(nodeTem.rightc);
return true;
? time : O(n)
? space : O(n)
? 1. the key of this algorithm is how can we process the same level of a tree and how we judge the same level nodes.
? 2. i have wrote the pseudocode and it did help me figure out how i'll write the code but it's hard for me to make sure the correctness of the pseudocode and i still debug my code as if the pseudocode is somehow pointless.how can i make the best of the pseudocode?
? 3. this is a rather explicit and strightforward method basicall just reinterpret the definition.
2. Recursion Version:
Description: ?
? Examine every node of the tree :
? if it has no children,then continue;
? if it has one child,then examine the child;
? if it has two children,then examine if the height of the two children is the same ?and then seperately examine the two children;
? until all the nodes are examined can we reach a conclusion.
Algoritm: SameLevel(node* root)
Input:a pointer of node pointing to a root of a (sub)tree.
Output:a bool which is true when all the leaves(if exsits) are at the same level and false vice versa.
int height(node* root);//return the height of the tree
if NodeTem.leftc == NULL && Node.rightc == NULL then
? ? return true
else if NodeTem.leftc != NULL && NodeTem.rightc == NULL then
? ? if SameLevel(NodeTem.leftc) then
? ? ? ? return true;
? ? else
? ? ? ? return false;
else if NodeTem.rightc != NULL && NodeTem.leftc == NULL then
? ? if SameLevel(NodeTem.rightc) then
? ? ? ? return true;
? ? else
? ? ? ? return false;
else
? ? if height(NodeTem.rightc) == height(NodeTem.leftc) && SameLevel(NodeTem.rightc) && SameLevel(NodeTem.leftc)
? ? ? ? return true;
? ? else
? ? ? ? return false;
|