LeetCode题解—填充二叉树节点右侧指针

码上积木

发布于 2021-04-16 10:32:23

4300

发布于 2021-04-16 10:32:23

文章被收录于专栏：码上积木码上积木

前言

今天继续看二叉树的算法：填充每个节点的下一个右侧节点指针

题目

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

解法一

题目什么意思呢？就是把完全二叉树的么一行用指针进行连接，类似这样：

      1  -> null
    /   \
   2  -> 3  -> null
  / \   / \
 4-> 5->6->7  -> null

所以我首先想到的办法就是遍历，用深度优先遍历每一层树结构，然后用集合存储再一一连接：

 public Node connect(Node root) {
  if(root==null) {
   return root;
  }
  //每一层都用queue保存
  LinkedList<Node> queue = new LinkedList<Node>();
  queue.add(root);
  //开始遍历树结构，当queue为空则遍历结束
  while(queue.size()>0) {
   int size = queue.size();
   //将列表的元素串联起来
   Node tmp = queue.get(0);
   for(int i=1;i<size;++i) {
    tmp.next = queue.get(i);
    tmp = queue.get(i);
   }
   //删除这一层树结构，并把树的下一层节点加到列表中
   for(int i=0;i<size;++i) {
    tmp = queue.remove();
    if(tmp.left!=null) {
     queue.add(tmp.left);
    }
    if(tmp.right!=null) {
     queue.add(tmp.right);
    }
   }
  }
  return root;
 }

这种解法就比较清晰，每次遍历树的一层结构，然后进行连接

复杂度

时间复杂度：O(n) 空间复杂度：O(n)

解法2

如果不用到单独的列表，也就是用常量级的空间可以完成这一题吗？

不用到列表辅助，如果一层只有两个节点，那么就可以写成：

root.left.next = root.right;

那对于一层多个节点，比如4个节点，8个节点的情况，就要垮父节点操作，这时候我们就要用到父节点的next进行遍历：

if (parenthead.next != null) {
    parenthead.right.next = parenthead.next.left;
}

所以，就能得出新的解法：

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return root;
        }
        
        // 从根节点开始
        Node leftmost = root;
        
        //遍历每一层，直到没有下层节点
        while (leftmost.left != null) {
            
            Node head = leftmost;
            
            //遍历当前这一层
            while (head != null) {
                
                // 连接第一个小树
                head.left.next = head.right;
                
                // 链接第二个小树，根据父节点的next
                if (head.next != null) {
                    head.right.next = head.next.left;
                }
                
                // 指针向后移动
                head = head.next;
            }
            
            // 去下一层的最左的节点
            leftmost = leftmost.left;
        }
        
        return root;
    }
}

复杂度

时间复杂度：O(n) 空间复杂度：O(1)

解法3

还有一种解法，就是递归，我们可以设计一种递归方法，每次传入两个节点，并且相连：

void connectTwo(Node node1, Node node2) {
    if (node1 == null || node2 == null) {
        return;
    }
    // 将传入的两个节点连接
    node1.next = node2;
}

然后调用递归方法的场景无非就是两个树结构，所以涉及到三种场景：

树1的左节点连接右节点
树1的右节点连接树2的左节点
树2的左节点连接右节点

所以得出以下解法：

 public Node connect(Node root) {
        if(root==null) return null;
        connectTwo(root.left,root.right);
        return root;
    }

    public void connectTwo(Node root1,Node root2) {
        if(root1==null)return;
        root1.next=root2;

        connectTwo(root1.left,root1.right);
        connectTwo(root1.right,root2.left);
        connectTwo(root2.left,root2.right);
    }

还可以对第二种场景，也就是树1的右节点连接树2的左节点进行优化，将两颗树的处理放到递归方法里面：

public Node connect(Node root) {
        if(root==null) return null;
        connection(root);
        return root;
    }
    public void connection(Node root){
        if(root.left == null) return;
        root.left.next=root.right;
        if(root.next != null){
            root.right.next=root.next.left;
        }
        connection(root.left);
        connection(root.right);
    }