算法练习

二叉树展开为链表(LeetCode 114 -- 使用递归遍历)

2020-02-24  本文已影响0人  倚剑赏雪

题目

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

例如,给定二叉树

    1
   / \
  2   5
 / \   \
3   4   6

将其展开为:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

解析

1.使用递归遍历,先将左右子树保存下来,再将左右子树的最后一个节点存下来
2.若有左子树,则将左子树置为空,右子树指向左子树,last指向左子树的最后一个节点
3.若有右子树,若左子树的最后一个节点不为空,则将左子树的右节点指向右节点,last指向右子树的最后一个节点

代码

    public void Flatten(TreeNode root)
    {
        TreeNode last = null;
        PreorderFlatten(root,ref last);
    }

    void PreorderFlatten(TreeNode node,ref TreeNode last)
    {
        if(node == null) return;
        if (node.left == null&&node.right == null)
        {
            last = node;
            return;
        }

        TreeNode left = node.left;//备份左右指针
        TreeNode right = node.right;
        TreeNode leftLast = null;//左右子树最后一个节点
        TreeNode rightLast = null;
        if (left != null)
        {
            PreorderFlatten(left,ref leftLast);//若有左子树,递归将左子树转换为单链表
            node.left = null;//左子树为空
            node.right = left;//右指针改变
            last = leftLast; //将该节点的last保存为左子树
        }

        if (right != null)//若有右子树,递归将右子树转换为单链表
        {
            PreorderFlatten(right, ref rightLast);
            if (leftLast != null)//若找到左子树的最后一个节点(有左子树)
            {
                leftLast.right = right;
            }

            last = rightLast;
        }
    }
上一篇 下一篇

猜你喜欢

热点阅读