【每日阅读】2020年11月10日-二叉树原地展开为链表

真诚的希望您能留言与我交流,这会对我有非常大的帮助!

链接

https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/

新得

这个题目注明了,需要原地展开,也就是不使用新得内存空间,使用原来二叉树的节点来展开。展开后的树其实特征很明显

  1. 每个节点只有右节点有值
  2. 新展开的树从上到下的节点顺序是先序遍历的顺序

树的题目一开始就往三种遍历(先序、中序、后序)顺序去想大概率会命中,这道题就是使用先序遍历的思路可以解决。

思路

当使用先序遍历的方式遍历每个节点时,将每次访问的节点从树上摘除,然后挂到新树上,再继续访问左子树,右子树,重复同样的操作(递归)即可。

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private TreeNode rightLastNode;

    /**
     * 先序遍历搞定树的展开
     */
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }

        TreeNode left = root.left;
        TreeNode right = root.right;

        if (rightLastNode != null) {
            rightLastNode.right = root;
        }

        rightLastNode = root;

        root.left = null;
        root.right = null;

        flatten(left);
        flatten(right);
    }
}

原创文章,作者:geekgao,如若转载,请注明出处:https://www.geekgao.cn/archives/2677

发表评论

登录后才能评论
GitHub
分享本页
返回顶部