本文共 1197 字,大约阅读时间需要 3 分钟。
本系列文章已全部上传至我的github,地址:
欢迎大家关注我的新浪微博, 欢迎转载,转载请注明出处
Given a binary tree, flatten it to a linked list in-place.
For example,
Given1 / \ 2 5 / \ \3 4 6The flattened tree should look like:
1 \ 2 \ 3 \ 4 \ 5 \ 6
题目大意:将一个二叉树转换成平树(google来的翻译)
看图就大概知道题目的意思了。 解题思路:flattened tree的顺序就是原树的前序遍历。所以可以定义一颗新树,按照前序遍历来生成右子树。 具体见代码:/** * 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* newroot = NULL;//新树的根节点 TreeNode* p = newroot;//循环中间变量 void flatten(TreeNode* root) { if(root==NULL) return; preorder(root);//前序遍历 //这里有个疑惑:为什么roor=newroot不行? root->right = newroot->right; root->left = NULL; } void preorder(TreeNode* root)//中序遍历 { TreeNode* temp = new TreeNode(root->val); if(newroot==NULL) newroot=temp;//保存根节点 else p->right=temp;//构造右子树 p = temp; if(root->left!=NULL) preorder(root->left); if(root->right!=NULL) preorder(root->right); }};