首页 > 代码库 > leetcode第一刷_ Flatten Binary Tree to Linked List
leetcode第一刷_ Flatten Binary Tree to Linked List
提示中说明了,改动后的链表相当于原树的前序遍历结果。前序遍历是根左右,因为要把转换后的左子树链接到根节点的右子树上,因此进入递归之后要先把节点的右子树保存下来,然后进入左子树,左子树转换后应该返回最后一个訪问的节点。这个节点的后继是根节点的转换后右子树。说起来很绕,可能看代码反而好一些。
注意一个问题是,不管如何。转换后的根节点一定要把左子树置空。要么会报错的。
TreeNode* preOrder(TreeNode *root){ if(!root||(!root->left&&!root->right)) return root; TreeNode *pre=NULL, *next; next = root->right; if(root->left){ root->right = root->left; pre = preOrder(root->left); } root->left = NULL; if(!next) return pre; if(pre) pre->right = next; return preOrder(next); } class Solution { public: void flatten(TreeNode *root) { preOrder(root); return; } };
leetcode第一刷_ Flatten Binary Tree to Linked List
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。