Leetcode114二叉树展开为链表

题目

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

例如，给定二叉树
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) {
        flatAndReturnTail(root);
    }
    /**
    * 此函数使用递归实现铺平功能，结果返回最后一个节点
    **/
    TreeNode* flatAndReturnTail(TreeNode* root){
        //如果为NULL或者左右都为NULL，就是此分支遍历完了
        if(!root || (!root->left && !root->right))
            return root;
        //如果只有左子树，就把左子树放在右子树上，然后处理右子树
        else if(root->left && !root->right){
            root->right = root->left;
            root->left = NULL;
            return flatAndReturnTail(root->right);
        //如果左右子树都存在
        }else if(root->left && root->right){
            
            TreeNode* p = root->right;
            //把左子树放在右子树上
            root->right = root->left;
            root->left = NULL;
            //获取“左子树”处理后的最后节点
            TreeNode* q = flatAndReturnTail(root->right);
            //把“左子树”最后节点接上“右子树”
            q->right = p;
            //处理“右子树”
            return flatAndReturnTail(p);
        //其他情况，只有右子树，则处理右子树即可
        }else
            return flatAndReturnTail(root->right);
    }
};