每日一题 2019 - 04 - 27
题目:
Given a binary tree, flatten it to a linked list in-place.
For example, given the following tree:
The flattened tree should look like:
1 2 3 4 5 6 7 8 9 10 11
|
1 2 3 4 5 6
|
解法:
这个题让把给出的二叉树转成一个链表,这个链表特征为:所有二叉树的结点链接在二叉树的右子树上,解题思路如下:
- 深层次遍历二叉树,找到最下层的左子节点
- 将左子分支加入到右子分支中,也即
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
|
class { public: void flatten(TreeNode* root) { if(root == NULL) { return ; } if(root->left) { flatten(root->left); } if(root->right) { flatten(root->right); } TreeNode* temp = root -> right ; root -> right = root -> left ; root -> left = NULL ; while(root->right) { root = root -> right ; } root -> right = temp ; } };
|
近期评论