Flatten Binary Tree to Linked List (DFS)

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

The flattened tree should look like:

class Solution{

public:

    void flatten(TreeNode *root) {

        if(root==NULL) return;

        TreeNode* p=root->left;

        if(p==NULL){

            flatten(root->right);

            return;

        }

        while(p->right!=NULL) p=p->right;

        TreeNode* temp=root->right;

        root->right=root->left;

        root->left=NULL;//一定不要忘记左子树要赋空

        p->right=temp;

        flatten(root->right);

        return;

    }

};

这种DFS画图最好理解了，下图是我的解题过程：

巴特西

Flatten Binary Tree to Linked List (DFS)

最新文章

热门文章