LeetCode 114. 二叉树展开为链表

给定一个二叉树，原地将它展开为链表。

例如，给定二叉树

      1    /    \  2      5 /   \       \3   4       6将其展开为：

1  \    2      \       3         \          4            \             5               \                 6

算法：我们每次在遍历的时候，先找到当前结点左子树最右下角的结点，然后让该结点指向当前结点的右子树，然后让当前结点的右指针指向当前结点的左子树，最后将当前结点的左指针置空即可。

/** * 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: void flatten(TreeNode* root) { auto now=root; while(now){ if(now->left){ auto p=now->left; while(p->right)p=p->right; p->right=now->right; now->right=now->left; now->left=NULL; } now=now->right; } } };

 

转载于:https://www.cnblogs.com/programyang/p/11167264.html