114. 二叉树展开为链表 (四种解法)

解法1：递归，从下至上先将深层次的左右子树转化为链表

关键步骤：

1：对带有左子树的节点，将其左右子树展开为链表。

2：找左子树最右的叶子节点，将右子树挂左子树最右叶子上。

3：将左子树换成右子树，左子树置空。

class Solution { public: void flatten(TreeNode* root) { if (NULL == root) return; flatten(root->right); //将右子树展开为链表 if (NULL == root->left) //若左子树为空，不用再操作 return; flatten(root->left); //将左子树展开为链表 TreeNode *rightTail = root->left; while (rightTail->right) rightTail = rightTail->right; //找左子树最右的叶节点 rightTail->right = root->right; //右子树挂左子树最右叶子上 root->right = root->left; //左子树换成右子树 root->left = NULL; //左子树置空 } };

解法2：非递归，从上至下一层层消除左子树

关键步骤：

1：从root层开始，一层层消除左子树

2：找左子树最右的叶子节点，将右子树挂左子树最右叶子上。

3：将左子树换成右子树，左子树置空。

class Solution { public: void flatten(TreeNode* root) { if (NULL == root) return; TreeNode *node, *rightTail; while (root) { if (NULL != root->left) { node = root->left; //对左子树进行操作 rightTail = node; while (rightTail->right) rightTail = rightTail->right; //找左子树的最右叶子节点 rightTail->right = root->right; //将右子树接到上述叶子节点的右子节点上 root->right = root->left; //将左子树改成右子树 root->left = NULL; //左子树置空 } root = root->right; } } };

解法3：利用栈，先序遍历，根节点开始一点点穿下一个较大的数，大数最后处理

关键步骤：

1：用一个pre指针指向当前链表最后一个节点。

2：大数的右子树先入栈，循环处理后，数越大，压的越深。

3：pre指针先连接左子树中的根节点（未处理的最小数）。

         循环处理后，通过pre指针一个个地串起了左子树的最小数（左子树左子节点），然后再串左子树的次小数（左子树右子节点），最后串右子树的较大数。

class Solution { public: void flatten(TreeNode* root) { if (NULL == root) return; stack<TreeNode*> sta; sta.push(root); TreeNode *pre = NULL, *node; while (!sta.empty()) { node = sta.top(); sta.pop(); if (NULL != pre) { pre->right = node; pre->left = NULL; } if (node->right) //先将大数压入栈，最后再处理 sta.push(node->right); if (node->left) //先处理左子树的小数，后入先出 sta.push(node->left); pre = node; //指向当前最小数的节点，一点一点连接较大数到右子树上 } } };

        这里，比较感谢牛客码友的解析。欢迎探讨！

解法四：若有左子树，将左子树转到右子树上，右子树若有则压栈

class Solution { public: void flatten(TreeNode* root) { if (NULL == root) return; stack<TreeNode*> sta; while (root || !sta.empty()) { if (root->left) { //有左子树情况 if (root->right) //右子树入栈 sta.push(root->right); root->right = root->left; root->left = NULL; } if (root->right) //有节点非空，就往下走一步 root = root->right; else { if (sta.empty()) //右节点空，备用栈空，结束 break; root->right = sta.top(); //从栈里找节点挂上去 sta.pop(); } } } };

         看示例，想到的一种最直接的方法！