Leetcode 114：Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example, given the following tree:

The flattened tree should look like:

这道题要求把二叉树展开成链表，根据展开后形成的链表的顺序分析出是使用先序遍历。想到树的遍历立马会联想到递归的方法。不过也不是一定要递归啦，这里用递归和非递归的两种方法来解决。

C++ void flatten(TreeNode* root) { if(root == nullptr) return; if(root->left)flatten(root->left); if(root->right)flatten(root->right); TreeNode* temp = root->right; root->right = root->left; root->left = nullptr; while(root->right)root = root->right; root->right = temp; }

下面这个是非递归的方法

C++ void flatten(TreeNode* root) { //非递归方法 TreeNode* cur = root; while(cur) { if(cur->left) { TreeNode* p = cur ->left; while(p->right)p = p->right; p->right = cur->right; cur->right = cur->left; cur->left = nullptr; } cur = cur->right; } }