首页 > 代码库 > 【leetcode】Flatten Binary Tree to Linked List

【leetcode】Flatten Binary Tree to Linked List

2024-07-07 17:28:14   219人阅读

分析：

问题是将给定的二叉树变换成令一种形式，这种类型的问题，其模式是，将左子树变换成某种形式，右子树也变换成这种形式，然后再与根结点按规定的方式连接起来，那么整体就变换完成了。这个题我们就可以采用这种形式，麻烦的地方就是在进行连接的时候，我们假设根为root，左子树变换后的根为root_left，右子树变换后的根为 root_right，那么连接的时候应该是root->right = root_left，再连接root_right的时候，应该是root_left所指向的一系列结点的最后一个结点和root_right连接，假设该结点为tail_left，那么就应该是tail_left->right = root_right。这样总体就连接好了。在具体连接的时候，可能要考虑某些结点为NULL的情况。
//
TreeNode *&link(TreeNode *&root)
	{
		if(root == NULL || root->left == NULL && root->right == NULL) 
			return root;
		TreeNode *root_left = NULL;
		TreeNode *root_right = NULL;
		root_left = link(root->left);
		root_right = link(root->right);
		if(root_left != NULL)
		{
			TreeNode *tail = root_left;
			//find the last one of root->left.
			while(tail->right) tail = tail->right;
			tail->right = root_right;
		}
		else
			root_left = root_right;
		root->right = root_left;
		root->left = NULL;
		return root;
	}
	void flatten(TreeNode *root) {
		if(root == NULL) return;
		root = link(root);
	}

我们再换个思路，题目中提示我们这种形式其实是树的先根遍历的结果，那么我们回想下基本先根遍历是怎么处理的，我们都是简单的将根结点的val值进行打印。现在如果可以用额外的空间，那么我们就可以将先根遍历中的根结点放到一个顺序容器中，然后将每个结点连起来就是题目要求的了，但是题目的意思很明显不希望这样做，但我们还是希望用这种形式，那怎么办呢？其实我们不难发现，转换后的树形式上就是个单链表，那么问题就转换成单链表的建立。
void preVisit(TreeNode*& pre, TreeNode*root)
	{
		if(root == NULL)
			return;
		TreeNode *right = root->right;
		TreeNode *left = root->left;
		root->left = NULL;
		if(pre == NULL)
			pre = root;
		else
		{
			pre->right = root;
			pre = root;
		}
		if(left)
			preVisit(pre, left);
		if(right)
			preVisit(pre, right);
	}

上面的代码就是典型的先根遍历的模板，只是模板中的万能visit函数做了一点稍微复杂的事情。
void flatten(TreeNode* root)
	{
		if(root = NULL) return;
		TreeNode *pre = NULL;
		preVisit(pre, root);
	}

总结：还是重复前面文章中反复说过的，树的基本遍历的模式一定要熟记于胸，很多衍生的问题都是可以套用模板的。


联系
我们