LeetCode Flatten Binary Tree to Linked List

LeetCode Flatten Binary Tree to Linked List

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

click to show hints.

Hints:If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.


把一棵二叉树展开成一个链表,链表还是借助树的数据结构,只不过是借用了树的右孩子指针作为链表的指针。

仔细观察发现新的链表的顺序和树的先序遍历的顺序一致,如果能使用额外的空间,则先序遍历后把节点存到数组中,然后依次链接起来。

如果不使用额外空间,则只能想办法在DFS时就建立好链接关系。先序遍历的顺序是根左右,但是这题为了方便,我们先对右孩子建立链表,然后把右孩子接到父亲的左孩子的最右下角的节点上。比如上图中,我们建立好5->6的链表之后,需要把它接到4号节点的右边。

         1
        / 
       2   
      / \   
     3   4   
          \
           5
            \
             6

所以针对右孩子,我们需要根据父节点找到父节点的左子树的最右下角的节点。但是针对左孩子时,因为此时右孩子已经建立好链表并且接到了左孩子正确的位置上,所以只需要把左孩子接到父亲的右孩子位置,并把原来的左孩子置空,下图就是把上图1的左子树放到了右边,左边置为空。

   1      
     \   
       2  
      / \   
     3   4   
          \
           5
            \
             6

完整代码如下:

class Solution2 {
public:
	void dfs(TreeNode* par, TreeNode* cur) {
		if (cur == NULL)return;
		if(par){
			if (cur == par->right) {
				if (par->left) {
					TreeNode* tmp = par->left;
					while (tmp->right)tmp = tmp->right;
					tmp->right = cur;
					par->right = NULL;
				}
			}
			else {
				par->right = cur;
				par->left = NULL;
			}
		}
		if (cur->right)dfs(cur, cur->right);
		if (cur->left)dfs(cur, cur->left);
	}
	void flatten(TreeNode* root) {
		dfs(NULL, root);
	}
};

本代码提交AC,用时6MS。

还有一种思路比这简单,上面的解法需要while循环查找左兄弟的最右下角的节点,如果我们在DFS中直接返回尾节点,就不需要while查找了。

假设某节点的左右子树T(root->left)和T(root->right)已经flatten成linked list了:

1
/    \
2     5
\       \
3      6 <- rightTail
\
4  <- leftTail

如何将root、T(root->left)、T(root->right) flatten成一整个linked list?显而易见:

leftTail->right = root->right;
root->right = root->left;
root->left = NULL;

这里需要用到已经flatten的linked list的尾部元素leftTail, rightTail。所以递归返回值应该是生成的整个linked list的尾部。

代码如下:

class Solution {
public:
	TreeNode* dfs(TreeNode* root) {
		if (!root)return NULL;
		TreeNode* leftTail = dfs(root->left);
		TreeNode* rightTail = dfs(root->right);
		if (root->left) {
			leftTail->right = root->right;
			root->right = root->left;
			root->left = NULL;
		}
		if (rightTail)return rightTail;
		if (leftTail)return leftTail;
		return root;
	}
	void flatten(TreeNode* root) {
		dfs(root);
	}
};

本代码提交AC,用时6MS。

Leave a Reply

Your email address will not be published. Required fields are marked *