114.二叉树展开为链表

链接：

114.二叉树展开为链表

思路：

对于节点A，其右子树作为左子树前序遍历最后一个叶子节点的有子树，再将节点A的左子树置为null

旋转过程.png

实现：

class Solution {
public:
    void flatten(TreeNode *root) {
        TreeNode *keyNode = root;

        while (keyNode != NULL) {
            TreeNode *leftChild = keyNode->left;
            TreeNode *rightChild = keyNode->right;
            if (leftChild != NULL) {
                TreeNode *targetNode = this->findRightChild(leftChild);
                targetNode->right = keyNode->right;
                keyNode->right = leftChild;
                keyNode->left = NULL;
            }
            if (keyNode->right != NULL) {
                keyNode = keyNode->right;
            }
            if (keyNode->left == NULL && keyNode->right == NULL) {
                break;
            }
        }
        keyNode = root;
        while (keyNode != NULL) {
            printf("%d\n", keyNode->val);
            keyNode = keyNode->right;
        }

    }

    TreeNode *findRightChild(TreeNode *targetNode) {
        TreeNode *key = targetNode;
        while (key->left != NULL || key->right != NULL) {
            if (key->right != NULL) {
                key = key->right;
            } else if (key->left != NULL) {
                key = key->left;
            } else {
                break;
            }

        }
        return key;

    }
};