这个题目之前做过了,但是由于思路不清晰,今天思路又卡了
比如:
0
1 2
3 4 5
6 7
1->2
3->4->5
6->7
参考数据结构:
struct TREE_NODE
{
TREE_NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL), pSib(NULL)
{}
int nVal;
TREE_NODE* pLft;
TREE_NODE* pRgt;
TREE_NODE* pSib;
};
对于每一个节点tnode,都要将其左右节点链接。如果没有右节点,则就要找和tnode同一层的节点,直到找到一个节点有左孩子或者右孩子,返回这个节点的孩子。
有一个问题要解决,在找和tnode同层的节点的孩子节点,必须保证tnode同层的所有节点已经链接了,用先左再右的递归不行,所以要用从右到左的递归。
TREE_NODE *find_next(TREE_NODE *root) { while(root = root->pSib) { if(root->pLft || root->pRgt) return root->pLft?root->pLft:root->pRgt; } return NULL; } void LinkLevelNodes(TREE_NODE *root) { if(!root) return ; if(root->pLft) root->pLft->pSib = root->pRgt?root->pRgt:find_next(root); if(root->pRgt) root->pRgt->pSib = find_next(root); LinkLevelNodes(root->pRgt); LinkLevelNodes(root->pLft); }