117. 填充每个节点的下一个右侧节点指针 II
问题描述
给定一个二叉树，填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
解题思路
这一题与116的不同之处在于，给定的二叉树不是完美二叉树。每个节点的左、右子节点有可能为空。因此引入队列来存储每一层节点的前后顺序。
代码实现1-递归
/*
// 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;
}
//1.利用已经建立好的next指针将下一层的所有非空节点读入队列
Queue<Node> level = new LinkedList<>();
Node temp = root;
while(temp != null){
if(temp.left != null){
level.add(temp.left);
}
if(temp.right != null){
level.add(temp.right);
}
temp = temp.next;
}
if(level.isEmpty()){
return root;
}
//2.连接队列中的前后元素
Node cur = level.remove();
while(!level.isEmpty()){
Node next = level.remove();
cur.next = next;
cur = next;
}
root.left = connect(root.left);
root.right = connect(root.right);
return root;
}
}
代码实现2-迭代
递归通过之后，想到其实也可以用迭代的方法来实现。每次迭代的操作是连接同一层的节点，下一次迭代的参数是本层首节点（即队列中的队头节点），迭代结束的条件是该层节点数为0。
class Solution {
public Node connect(Node root) {
if(root == null){
return root;
}
Node levelFirst = root;
Queue<Node> level = new LinkedList<>();
while(level.isEmpty()){
//1.将下一层的所有非空节点读入队列，利用已经建立好的next指针
Node temp = levelFirst;
while(temp != null){
if(temp.left != null){
level.add(temp.left);
}
if(temp.right != null){
level.add(temp.right);
}
temp = temp.next;
}
if(level.isEmpty()){
//下一层没有节点时，循环结束
break;
}
//2.连接队列中的前后元素
Node cur = level.remove();
//队列中的第一个元素即为下一层的首个节点
levelFirst = cur;
while(!level.isEmpty()){
Node next = level.remove();
cur.next = next;
cur = next;
}
}
return root;
}
}
代码从递归改写为迭代之后，运行时间从21ms下降到了1ms。=.=
image.png
129. 求根到叶子节点数字之和
问题描述
给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。
例如，从根到叶子节点路径 1->2->3 代表数字 123。
计算从根到叶子节点生成的所有数字之和。
说明: 叶子节点是指没有子节点的节点。
解题思路
每个节点的路径贡献数值 = 父节点*10 + 节点本身的值
代码实现
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int sumNumbers(TreeNode root) {
return traversal(root,0);
}
public int traversal(TreeNode root, int parentVal){
if(root == null){
return 0;
}
//叶子节点
int sum = root.val + parentVal * 10;
if(root.left == null && root.right == null){
return sum;
}
return traversal(root.left, sum) + traversal(root.right, sum);
}
}
