leetcode每日一题(2020.09.28) 117. 填充每个节点的下一个右侧节点指针 II

leetcode每日一题汇总

117. 填充每个节点的下一个右侧节点指针 II(中等)

考察层序遍历

安安：层序遍历

/* // Definition for a Node. class Node { public int val; public Node left; public Node right; public Node next; public Node() {} public Node(int _val) { val = _val; } public Node(int _val, Node _left, Node _right, Node _next) { val = _val; left = _left; right = _right; next = _next; } }; */ /* 遍历每一层，以next指针连接相邻的两个节点，最后一个节点的next指针为null */ //2020.10.4 anan class Solution { public Node connect(Node root) { if(root == null) return null; Queue<Node> queue = new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()){ int n = queue.size(); Node pre = null; //按层遍历 for(int i = 0; i < n; i++){ //每一层的第一个节点当做是pre节点 if(i == 0){ pre = queue.poll(); if(pre.left != null) queue.offer(pre.left); if(pre.right != null) queue.offer(pre.right); }else{ //前一个节点的next指针指向当前节点 Node node = queue.poll(); pre.next = node; pre = node; if(node.left != null) queue.offer(node.left); if(node.right != null) queue.offer(node.right); } } pre.next = null; } return root; } }

官解：自己代码的优化，将每一层的第一个节点和其他节点一起考虑

/* // Definition for a Node. class Node { public int val; public Node left; public Node right; public Node next; public Node() {} public Node(int _val) { val = _val; } public Node(int _val, Node _left, Node _right, Node _next) { val = _val; left = _left; right = _right; next = _next; } }; */ /* 遍历每一层，以next指针连接相邻的两个节点，最后一个节点的next指针为null */ class Solution { public Node connect(Node root) { if(root == null) return null; Queue<Node> queue = new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()){ int n = queue.size(); Node pre = null; //按层遍历 for(int i = 0; i < n; i++){ Node node = queue.poll(); if(pre != null){ pre.next = node; } pre = node; if(node.left != null) queue.offer(node.left); if(node.right != null) queue.offer(node.right); } //pre.next = null; 这句可以不写，因为默认都是null } return root; } }