D***0
发帖数: 138 | 1 二面，现在真是店面还流行二进宫，依然还是做题，然后onsite还是做题，把做题进行
到底吧。
从昨晚接到recruiter的email通知换把一个国人大哥换成了不知哪国人，就有不祥预感
，另外一个是刚加入的一个小三姐。本来以为是这个senior出题，这小三姐在旁听着，
结果这大哥上来就说，翠花，上酸菜吧，小三姐可是毫不客气的把一道新题无情的砸向
了脆弱心灵的我（:)大家别扔鸡蛋啊），废话少说，书归正文：
Given a binary tree where all the right nodes are either empty or leaf nodes
, flip it upside down and turn it into a tree with left leaf nodes.
In the original tree, if a node has right child, it must has left child.
for example, turn these:
1 1
/ /
2 3 2 3
/
4
/
5 6
into these:
1 1
/ /
2---3 2---3
/
4
/
5---6
where 5 is the new root node for the left tree, and 2 for the right tree.
oriented correctly:
5 2
/ /
6 4 3 1
2
/
3 1
她说这个他们新题中的一道，可见大家以后有好几壶够喝的了。
最后磕磕绊绊的总是做出来了。
带头大哥说，来变个型，条件一样，给哥整成这样:
1 1
/ /
2 2
/
4 3 3
/
5
6
哎，实力有限，遇到新题就像遇见丈母娘一样，求个bless，能给个onsite吧。 | a***d
发帖数: 5 | 2 尝试写一个
TreeNode* ConvertTree(TreeNode *root)
{
if(!root) return NULL;
if(!root->left && !root->right) return root;
TreeNode* res=ConvertTree(root->left);
root->left->left=root->right;
root->left->right=root;
root->left=root->right=NULL;
return res;
} | l******6
发帖数: 340 | 3 TreeNode* upDown(TreeNode* root)
{
if(!root)
return root;
TreeNode* rightCousin = NULL;
TreeNode* parent = NULL;
TreeNode* temp;
while(root)
{
temp = root -> left;
root -> left = rightCousin;
rightCousin = root -> right;
root -> right = parent;
parent = root;
root = temp;
}
if(rightCousin)
{
rightCousin->left = parent;
return rightCousin;
}
return parent;
} | u*****o
发帖数: 1224 | | a********9
发帖数: 129 | | t******i
发帖数: 483 | | c********e
发帖数: 186 | | D**********d
发帖数: 849 | 8 Node* Insert(Node* root, Node* n){
if(!root) return root;
Node*t = root->right;
root->right = n;
if(root->left){
return Insert(root->left,t);
}else{
return root;
}
}
// initially call Node* NewRoot = Insert(root,NULL); | D****3
发帖数: 611 | | m**********4
发帖数: 774 | 10 多谢LZ分享。试着写了一会儿，花了挺长时间才想清楚。估计要是被面肯定挂了，时间
太长要是三姐再干扰干扰根本没可能想清楚。
JAVA:
Iterative version, 应该和reverse linkedlist差不多，但要多记录几个NODE的值
public TreeNode convert(TreeNode tn){
if (tn == null)
return tn;
TreeNode curr = tn;
TreeNode prevLeft = null;
TreeNode prevRight = null;
while (curr != null){
TreeNode currLeft = curr.left;
TreeNode currRight = curr.right;
curr.left = prevRight;
curr.right = prevLeft;
prevLeft = curr;
curr = currLeft;
prevRight = currRight;
}
return prevLeft;
}
Recursive:
JAVA木有指针，不好改动，所以做一个NodePair class记录转换过的HEAD 和TAIL。
class NodePair{
TreeNode head;
TreeNode tail;
NodePair(TreeNode h, TreeNode t){
head = h;
tail = t;
}
}
public NodePair convert2(TreeNode node, TreeNode rightNode){
TreeNode next = node.left;
if (next == null){
node.left = rightNode;
return new NodePair(node, node);
}else{
TreeNode rightTmp = node.right;
NodePair np = convert2(next, rightTmp);
node.left = rightNode;
node.right = null;
np.tail.right = node;
return new NodePair(np.head, node);
}
}
nodes
【在 D***0 的大作中提到】
: 二面，现在真是店面还流行二进宫，依然还是做题，然后onsite还是做题，把做题进行
: 到底吧。
: 从昨晚接到recruiter的email通知换把一个国人大哥换成了不知哪国人，就有不祥预感
: ，另外一个是刚加入的一个小三姐。本来以为是这个senior出题，这小三姐在旁听着，
: 结果这大哥上来就说，翠花，上酸菜吧，小三姐可是毫不客气的把一道新题无情的砸向
: 了脆弱心灵的我（:)大家别扔鸡蛋啊），废话少说，书归正文：
: Given a binary tree where all the right nodes are either empty or leaf nodes
: , flip it upside down and turn it into a tree with left leaf nodes.
: In the original tree, if a node has right child, it must has left child.
: for example, turn these:
| y***n
发帖数: 1594 | | p****o
发帖数: 46 | 12 it is quite like to process a linkedlist.
不过没太看懂变型的要求, 有什么区别?
nodes
【在 D***0 的大作中提到】
: 二面，现在真是店面还流行二进宫，依然还是做题，然后onsite还是做题，把做题进行
: 到底吧。
: 从昨晚接到recruiter的email通知换把一个国人大哥换成了不知哪国人，就有不祥预感
: ，另外一个是刚加入的一个小三姐。本来以为是这个senior出题，这小三姐在旁听着，
: 结果这大哥上来就说，翠花，上酸菜吧，小三姐可是毫不客气的把一道新题无情的砸向
: 了脆弱心灵的我（:)大家别扔鸡蛋啊），废话少说，书归正文：
: Given a binary tree where all the right nodes are either empty or leaf nodes
: , flip it upside down and turn it into a tree with left leaf nodes.
: In the original tree, if a node has right child, it must has left child.
: for example, turn these:
| s*********9
发帖数: 53 | |
|
