网站建设专业简介,台州网站制作计划,深圳市宝安区中心医院是三甲吗,高端网站配色leetcode 116. 填充每个节点的下一个右侧节点指针
题目
给定一个 完美二叉树 #xff0c;其所有叶子节点都在同一层#xff0c;每个父节点都有两个子节点。二叉树定义如下#xff1a;
struct Node { int val; Node *left; Node *right; Node *next; } 填充它的每个 next …leetcode 116. 填充每个节点的下一个右侧节点指针
题目
给定一个 完美二叉树 其所有叶子节点都在同一层每个父节点都有两个子节点。二叉树定义如下
struct Node { int val; Node *left; Node *right; Node *next; } 填充它的每个 next 指针让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点则将 next 指针设置为 NULL。
初始状态下所有 next 指针都被设置为 NULL。
思路
这道题假设用层序遍历开一个队列来做其实非常的简单但是他既然说了进阶要不开额外空间这一点就值得考量了。实际上就是怎样才能去掉这个队列呢那就必然得拿到下一个节点这个可以借助父节点的next来做因为遍历到下一层的时候父节点的next是已知的。所以就一目了然了这道题除了迭代外还可以用递归。
代码
// 迭代
/*
// 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;}
};
*/class Solution {public Node connect(Node root) {if (root null) {return root;}// DequeNode queue new ArrayDequeNode();// queue.offerLast(root);Node node root;while (node.left ! null) {Node firstnode node;while (node ! null) {if (node.left ! null) {node.left.next node.right;}if (node.next ! null) {node.right.next node.next.left;}node node.next;}node firstnode.left;}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;}
};
*/class Solution {public Node connect(Node root) {if (root null) {return null;}if (root.left ! null) {root.left.next root.right;root.right.next root.next null ? null : root.next.left;connect(root.left);connect(root.right);}return root;}
}
