赞
踩
给你二叉树的根结点 root
,请你将它展开为一个单链表:
展开后的单链表应该同样使用 TreeNode
,其中 right
子指针指向链表中下一个结点,而左子指针始终为 null
。
展开后的单链表应该与二叉树先序遍历顺序相同。
示例 1:
输入:root = [1,2,5,3,4,null,6] 输出:[1,null,2,null,3,null,4,null,5,null,6]
示例 2:
输入:root = [] 输出:[]
示例 3:
输入:root = [0] 输出:[0]
- /**
- * Definition for a binary tree node.
- * struct TreeNode {
- * int val;
- * TreeNode *left;
- * TreeNode *right;
- * TreeNode() : val(0), left(nullptr), right(nullptr) {}
- * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
- * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
- * };
- */
- class Solution {//时间复杂度O(N),空间复杂度O(1)
- public:
- 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;//向右孩子遍历
- }
- }
- };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。