Flatten Binary Tree to Linked List--LeetCode

太过爱你忘了你带给我的痛 2022-08-07 12:37 8阅读 0赞

# 题目： #

Given a binary tree, flatten it to a linked list in-place.

For example,  
Given

1
            / \
           2   5
          / \   \
         3   4   6

The flattened tree should look like:

1
        \
         2
          \
           3
            \
             4
              \
               5
                \
                 6

思路：从遍历的顺序上是前序遍历的结果，那么使用前序遍历，在前序遍历的过程中改变树结构，对于当前节点，是作为一个新的链表的头部，然后递归调用初始化左子树，递归调用右子树，为了能够连接，还得记住链表的尾部，当前节点的右子树是左子树改造后的链表的头节点，左子树的尾部后端是右子树的头部。

在实现的时候需要注意，最后的连接需要注意查看是否为空的操作。

void helper_list(BinTree*& root,BinTree*& head,BinTree*& tail)
    {
    	if(root == NULL ||(root->right == NULL && root->left == NULL))
    	{
    		head = root;
    		tail = root;
    		return ;
    	}
     	head = root;
    	BinTree* left_head = root->left;
    	head->left = NULL;
    	BinTree* left_tail = NULL;
    	
    	BinTree* right_head = root->right;
    	BinTree* right_tail = NULL;
    	
    	helper_list(left_head,left_head,left_tail);
    	helper_list(right_head,right_head,right_tail);
    	
    	
    	if(left_head != NULL)
    		head->right = left_head;
    	else
    		head->right = right_head;
    	
    	if(left_tail != NULL)
    		left_tail->right = right_head;
    	
    	if(right_tail != NULL)
    		tail = right_tail;
    	else
    		tail = left_tail;
    }
    
    BinTree* LinkedList(BinTree* root)
    {
    	if(root == NULL)
    		return NULL;
    	BinTree * head=NULL,*tail=NULL;
    	helper_list(root,head,tail);
    	return head;
    }