美文网首页
T114、二叉树展开为链表

T114、二叉树展开为链表

作者: 上行彩虹人 | 来源:发表于2020-09-10 18:20 被阅读0次

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

例如,给定二叉树

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

1

2

3

4

5

6

二叉树的问题要第一反应过来使用递归求解。
这题参考了评论区大神给出的答案
在还没操作节点右子树前,不能破坏该节点的右子树指向。所以采用后序遍历。

    public void flatten(TreeNode root) {
        if(root == null) return;
        flatten(root.left);
        flatten(root.right);
        TreeNode tmp = root.right;
        root.right = root.left;
        root.left = null;
        while(root.right != null) root = root.right;
        root.right = tmp;
    }

相关文章

网友评论

      本文标题:T114、二叉树展开为链表

      本文链接:https://www.haomeiwen.com/subject/geopektx.html