中序遍历
考虑使用中序遍历访问树的各节点 cur ;并在访问每个节点时构建 cur 和前驱节点 pre 的引用指向
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* pre = NULL, *head = NULL;
TreeNode* convert(TreeNode* root) {
if(root == NULL) return NULL;
dfs(root);
return head;
}
void dfs(TreeNode* cur)
{
if(!cur) return;
dfs(cur -> left);
if(!pre)
{
head = cur;
}
else
{
cur->left = pre;
pre->right = cur;
}
pre = cur;
dfs(cur -> right);
}
};
可以少一个临时指针
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode *pre = NULL;
TreeNode* convert(TreeNode* root) {
if(root == NULL) return NULL;
dfs(root);
while(root && root -> left) root = root -> left;
return root;
}
void dfs(TreeNode* cur)
{
if(!cur) return;
dfs(cur -> left);
if(pre)
{
cur->left = pre;
pre->right = cur;
}
pre = cur;
dfs(cur -> right);
}
};
不使用临时指针 用个pair 两节点 第一个节点表示当前子树最左侧节点 第二个节点表示当前子树最右侧节点 访问根节点 访问左子树 访问右子树 每次递归后 拼接三部分
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* convert(TreeNode* root) {
if(root == NULL) return NULL;
auto sides = dfs(root);
return sides.first;
}
pair<TreeNode*, TreeNode*> dfs(TreeNode* root)
{
if(!root->left && !root->right) return {root,root};
if(root->left && root->right)
{
auto lsides = dfs(root->left), rsides = dfs(root->right);
lsides.second->right = root, root->left = lsides.second;
rsides.first->left = root, root->right = rsides.first;
return {lsides.first, rsides.second};
}
if(root->left)
{
auto lsides = dfs(root->left);
lsides.second->right = root, root->left = lsides.second;
return {lsides.first, root};
}
if(root->right)
{
auto rsides = dfs(root->right);
rsides.first->left = root, root->right = rsides.first;
return {root, rsides.second};
}
}
};
注意 剑指 Offer 36. 二叉搜索树与双向链表
是双向循环列表 注意还要把首位相连 要用临时指针记录
第三种写法 最开始可以加一个判断当遍历到的节点是空节点情况 也可以不加 因为包含在了第一个if判断当中了返回的是{NULL, NULL}