leetcode114.二叉树展开为链表

leetcode114.二叉树展开为链表

二月 23, 2020

leetcode114. 二叉树展开为链表

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

例如，给定二叉树

  1
 / \
 2   5
/ \   \
3   4   6
将其展开为：

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

原地的定义：随着数据量的变化，我的存储空间应该不变。所以我觉得应该是不让用栈做的。

前序遍历解法

写在注释里面了.一定要注意 左子树置空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void flatten(TreeNode root) {
        if(root==null)return ;
        TreeNode tmp=root.right;
        root.right=root.left;
		//先把左子树放到当前节点的右节点
        flatten(root.left);//处理左子树
        root.left=null;
		//左子树置空
        TreeNode p=root;
        while(p.right!=null)
            p=p.right;
        p.right=tmp;
		//把原来的右子树放到最后一个节点的后面
        flatten(tmp);//处理右子树
    }

这道题我写完还半信半疑的提交，没想到他过了，这就是题感吗，我终于也点出这个技能了
leetcode 33/100