【leetcode】Flatten Binary Tree to Linked List （middle）

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

For example,
Given

The flattened tree should look like:

思路：

用先序遍历，得到的是从小到大的顺序。把先序遍历变形一下：

void flatten(TreeNode* root) {

        if(NULL == root) return;

        vector<TreeNode *> v;

        v.push_back(root);

        TreeNode * pCur = NULL;

        TreeNode * p = NULL;

        while(!v.empty())

        {

            pCur = p = v.back();

            while(NULL != p->left)  //向左移动时只要把当前指针移动即可，因为是按照从小大的顺序的

            {

                v.push_back(p->left);

                pCur = p = p->left;

            }

            while(!v.empty() && (p = v.back()->right) == NULL) //找到下一个要处理的元素，一定是一个右子树

                v.pop_back();

            if(!v.empty())

                v.pop_back();

            if(p != NULL)  //把待处理的右子树连在当前已经铺平的数的左子树上

            {

                v.push_back(p);

                pCur->left = p;

            }

        }

        p = root;

        while(p != NULL) //镜像，全部转移到右子树上

        {

            p->right = p->left;

            p->left = NULL;

            p = p->right;

        }

    }

我发现，我太依赖非递归了，其实有的时候用递归更好。比如大神的版本：

private TreeNode prev = null;

public void flatten(TreeNode root) {

    if (root == null)

        return;

    flatten(root.right);

    flatten(root.left);

    root.right = prev;

    root.left = null;

    prev = root;

}

先把右子树放平，再把左子树放平。因为每次都先处理右子树，所以prev是数值从大到小的一个记录，每次prev都是恰比当前根节点大一点的那个指针的位置。（不大好理解）

下面这个，跟上面的思路很像，但是会容易理解很多：

public void flatten(TreeNode root) {

        if (root == null) return;

        TreeNode left = root.left;

        TreeNode right = root.right;

        root.left = null;

        flatten(left);

        flatten(right);

        root.right = left;

        TreeNode cur = root;

        while (cur.right != null) cur = cur.right;

        cur.right = right;

    }

也是先铺平右子树，再铺平左子树。一定是右子树的值大于左子树，所以先把左子树连接到根节点右侧，再把右子树连在后面。这个代码平铺左右子树的顺序没限制。反过来也行。

上面思路的非递归版本：也是需要想半天才能看懂的。每次先把紧接着子树连好，其他代码都是从叶节点开始连接，这个是从根节点开始的。

public void flatten(TreeNode root) {

        if (root == null) return;

        Stack<TreeNode> stk = new Stack<TreeNode>();

        stk.push(root);

        while (!stk.isEmpty()){

            TreeNode curr = stk.pop();

            if (curr.right!=null)

                 stk.push(curr.right);

            if (curr.left!=null)

                 stk.push(curr.left);

            if (!stk.isEmpty())

                 curr.right = stk.peek();

            curr.left = null;  // dont forget this!!

        }

    }

秒客网

【leetcode】Flatten Binary Tree to Linked List （middle）

相关文章