116. Populating Next Right Pointers in Each Node

Link

難易度 : Medium

依照對岸Carl大神的練習順序，接下來會連做10題類似觀念的題目，題號如下 :

• 102.二叉树的层序遍历
• 107.二叉树的层次遍历II
• 199.二叉树的右视图
• 637.二叉树的层平均值
• 429.N叉树的层序遍历
• 515.在每个树行中找最大值
• 116.填充每个节点的下一个右侧节点指针
• 117.填充每个节点的下一个右侧节点指针II
• 104.二叉树的最大深度
• 111.二叉树的最小深度
  那麼就直接開始吧!!!

題目給予一個"perfect binary tree"並且node新增一個"next"的指標，要求我們將各個node的next指向"node右方的node"

思路的話其實就是在遍尋節點的過程，紀錄前一次探詢到的node，並且將前一個node指向當前的node。

    class Solution
    {
        public Node connect(Node root)
        {
            Queue<Node> queue = new LinkedList<Node>();
            Node current;
            if(root==null) 
            {
                return root;
            }
            queue.add(root);
            while(!queue.isEmpty()) 
            {
                int size = queue.size();
                Node tmp=null;
                //遍尋此層數量的所有node 之後加入的不與理會
                for(int i=0;i<size;i++) 
                {
                    current = queue.poll();
                    if(current.left!=null) 
                    {
                        queue.add(current.left);
                    }
                    if(current.right!=null) 
                    {
                        queue.add(current.right);
                    }
                    if(tmp!=null) 
                    {
                        tmp.next=current;
                    }
                    tmp=current;
                }
            }
            return root;
        }
    }

可以看到效率還可以，可是沒有非常好，那麼要怎麼做可以優化效率呢?
關鍵的地方就在於題目中的一個詞

perfect binary tree

也就是代表

若是node有子節點，則必定有兩個滿的節點

因此思路上就可以變成

1. 若root.left!=null，則將left指向right
2. 若有right，則
   A. 先判斷root.next是否為null
   B. 不為null的話，將right指向root.next.left

    class Solution
    {
        public Node connect(Node root)
        {
            if(root==null) 
            {
                return root;
            }
            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);
            return root;
        }
    }