leetcode의 Flatten Binary Tree to Linked List

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

사고방식: 두 갈래 나무를 먼저 훑어보고 왼쪽 나무를 빈 노드로 하는 왼쪽 나무를 뒤에 있는 노드로 가리키고 모든 오른쪽 나무를 왼쪽 나무로 가리킨다

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void flatten(TreeNode *root)
{
	if(!root || (!root->left && !root->right))return;
	TreeNode* pre = NULL,*p = root;
	stack<TreeNode*> stk;
	while (p || !stk.empty())// 
	{
		while (p)
		{
			stk.push(p);
			p = p ->left;
		}
		p = stk.top();
		stk.pop();
		if(!p ->left)pre = p;
		p = p->right;
		if(p)pre->left = p;
	}
	p = root;
	while (p)
	{
		p->right = p->left;
		p->left = NULL;
		p = p->right;
	}
}

검지offer의 이원 찾기 트리를 정렬된 쌍방향 체인표로 바꾸는 것을 가리킨다
제목: 2원 찾기 트리를 입력하여 2원 찾기 트리를 정렬된 양방향 체인 테이블로 변환합니다.바늘의 방향만 조정하려면 새 결점을 만들 수 없습니다.
분석: 우리는 중간 순서로 나무 전체를 두루 돌아다닐 수 있다.이 방식에 따라 나무를 두루 돌아다니며 비교적 작은 결점을 먼저 방문한다.만약 우리가 매 결점을 방문할 때마다 이전에 방문한 결점이 정렬 양방향 체인 테이블로 조정되었다고 가정한다면, 우리는 현재 결점을 조정하는 바늘을 체인 테이블의 끝에 연결할 것이다.모든 결점을 방문한 후, 나무 전체가 정렬 양방향 체인 시계로 바뀌었다

TreeNode* convertTreeToDoubleList(TreeNode* root,TreeNode* &lastNode)
{
	if(!root)return root;
	TreeNode* curNode = root;
	TreeNode* head = convertTreeToDoubleList(root->left,lastNode);// ， 

	curNode ->left = lastNode;// 
	if(lastNode)lastNode->right = curNode;// 
	lastNode = curNode;// 
	if(!head)head = curNode;

	TreeNode* lHead  = convertTreeToDoubleList(root->right,lastNode);// ， 
	curNode->right  = lHead;
	if(lHead)lHead->left = curNode;

	return head;
}

TreeNode* convertTreeToDoubleList(TreeNode* root)
{
	TreeNode* lastNode = NULL;
	return convertTreeToDoubleList(root,lastNode);
}