在每个节点填充向右的指针 Populating Next Right Pointers in Each Node

2018-08-09 16:01:40

一、Populating Next Right Pointers in Each Node

问题描述：

问题求解：

由于是满二叉树，所以很好填充。

    public void connect(TreeLinkNode root) {

        if (root != null) {

            if (root.left != null) root.left.next = root.right;

            if (root.right != null && root.next != null) root.right.next = root.next.left;

            connect(root.left);

            connect(root.right);

        }

    }

二、Populating Next Right Pointers in Each Node II

问题描述：

问题求解：

本题中因为不再是满二叉树，因此不能简单的使用先序遍历进行求解，因为先序遍历是有先后顺序的，因此单纯采用先序遍历会出现丢失的现象。因此只能使用按行求解。

    public void connect(TreeLinkNode root) {

        if (root == null) return;

        TreeLinkNode dummy = new TreeLinkNode(-1);

        for (TreeLinkNode cur = root, pre = dummy; cur != null; cur = cur.next) {

            if (cur.left != null) {

                pre.next = cur.left;

                pre = pre.next;

            }

            if (cur.right != null) {

                pre.next = cur.right;

                pre = pre.next;

            }

        }

        connect(dummy.next);

    }

巴特西

在每个节点填充向右的指针 Populating Next Right Pointers in Each Node

最新文章

热门文章