合并二叉樹、拷貝二叉樹

題目：已知任意兩顆二叉樹tree1,tree2,合并為一個新的二叉樹。重疊的節點值疊加，非疊加的節點，直接作為新樹的節點

tree1
			  1
			/   \
		   2     3
          /
		 4

                            ---------\                        6(1+5)
                            ---------/                       / \
                                                            8   10
           tree2                                           /    /
			5                                             4    8
		  /   \                                        
		 6     7
		      /
			 8


struct TreeNode
{
	int nValue;
	TreeNode* pLeft;
	TreeNode* pRight;

	void init(int value)
	{
		nValue = value;
		pLeft = nullptr;
		pRight = nullptr;
	}
};
           

一、遞歸方案

// 遞歸合并樹
TreeNode* treeMerge(TreeNode *treeOne, TreeNode *treeTwo)
{
	if (treeOne == nullptr)
	{
		return treeTwo;
	}
	if (treeTwo == nullptr)
	{
		return treeOne;
	}
	TreeNode* newTree = (TreeNode*)malloc(sizeof(struct TreeNode));
	newTree->init(treeOne->nValue + treeTwo->nValue);
	newTree->pLeft = treeMerge(treeOne->pLeft, treeTwo->pLeft);
	newTree->pRight = treeMerge(treeOne->pRight, treeTwo->pRight);

	return newTree;
}
           

// 遞歸拷貝樹
TreeNode* copyTree(TreeNode *pTree)
{
	if (pTree == nullptr)
	{
		return nullptr;
	}

	TreeNode* newTree = (TreeNode*)malloc(sizeof(struct TreeNode));
	newTree->init(pTree->nValue);

	newTree->pLeft = copyTree(pTree->pLeft);
	newTree->pRight = copyTree(pTree->pRight);

	return newTree;
}
           

二、非遞歸拷貝樹--邏輯就是  廣度周遊

// 非遞歸
TreeNode *treeMerge2(TreeNode *treeOne, TreeNode *treeTwo)
{
	if (treeOne == nullptr) 
	{
		return treeTwo;
	}

	if (treeTwo == nullptr) 
	{
		return treeOne;
	}
	TreeNode* newTree = (TreeNode*)malloc(sizeof(struct TreeNode));
	newTree->init(treeOne->nValue + treeTwo->nValue);


	queue<TreeNode*> q;
	queue<TreeNode*> queue1;
	queue<TreeNode*> queue2;

	q.push(newTree);
	queue1.push(treeOne);
	queue2.push(treeTwo);

	while (!queue1.empty() && !queue2.empty())
	{
		TreeNode* node = q.front();
		TreeNode* node1 = queue1.front();
		TreeNode* node2 = queue2.front();

		q.pop();
		queue1.pop();
		queue2.pop();

		TreeNode* left1 = node1->pLeft;
		TreeNode* left2 = node2->pLeft;
		TreeNode* right1 = node1->pRight;
		TreeNode* right2 = node2->pRight;

		if (left1 != nullptr || left2 != nullptr)
		{
			if (left1 != nullptr && left2 != nullptr)
			{
				TreeNode* left = (TreeNode*)malloc(sizeof(struct TreeNode));
				left->init(left1->nValue + left2->nValue);

				node->pLeft = left;
				q.push(left);
				queue1.push(left1);
				queue2.push(left2);
			}
			else if (left1 != nullptr)
			{
				node->pLeft = copyTree2(left1);
			}
			else if (left2 != nullptr)
			{
				node->pLeft = copyTree2(left2);
			}
		}
		if (right1 != nullptr || right2 != nullptr)
		{
			if (right1 != nullptr && right2 != nullptr)
			{
				TreeNode* right = (TreeNode*)malloc(sizeof(struct TreeNode));
				right->init(right1->nValue + right2->nValue);

				node->pRight = right;
				q.push(right);
				queue1.push(right1);
				queue2.push(right2);
			}
			else if (right1 != nullptr)
			{
				node->pRight = copyTree2(right1);
			}
			else
			{
				node->pRight = copyTree2(right2);
			}
		}
	}

	return newTree;
}
           

// 非遞歸拷貝樹
TreeNode *copyTree2(TreeNode *pTree)
{
	if (pTree == nullptr)
	{
		return nullptr;
	}
	TreeNode* pTempLeft = nullptr;
	TreeNode* pTempRight = nullptr;

	TreeNode* newTree = (TreeNode*)malloc(sizeof(struct TreeNode));
	newTree->init(pTree->nValue);

	queue<TreeNode*> treeQueue;
	treeQueue.push(pTree);

	queue<TreeNode*> copyQueue;
	copyQueue.push(newTree);

	while (!treeQueue.empty())
	{
		TreeNode* node1 = treeQueue.front();
		treeQueue.pop();

		TreeNode* copyNode = copyQueue.front();
		copyQueue.pop();

		if (node1->pLeft != nullptr)
		{
			treeQueue.push(node1->pLeft);

			// 構造左節點
			copyNode->pLeft = (TreeNode*)malloc(sizeof(struct TreeNode));
			copyNode->pLeft->init(node1->pLeft->nValue);

			copyQueue.push(copyNode->pLeft);
		}

		if (node1->pRight != nullptr)
		{
			treeQueue.push(node1->pRight);

			// 構造右節點
			copyNode->pRight = (TreeNode*)malloc(sizeof(struct TreeNode));
			copyNode->pRight->init(node1->pRight->nValue);

			copyQueue.push(copyNode->pRight);
		}
	}

	return newTree;
}