红河做网站的公司,对网站建设的描述,全国门户网站有哪些,贵阳能做网站的公司有哪些一、题目 117. 填充每个节点的下一个右侧节点指针 II - 力扣#xff08;LeetCode#xff09; 给定一个二叉树#xff1a; struct Node {int val;Node *left;Node *right;Node *next;
} 填充它的每个 next 指针#xff0c;让这个指针指向其下一个右侧节点。如果找不到下一个…一、题目 117. 填充每个节点的下一个右侧节点指针 II - 力扣LeetCode 给定一个二叉树 struct Node {int val;Node *left;Node *right;Node *next;
} 填充它的每个 next 指针让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点则将 next 指针设置为 NULL 。 初始状态下所有 next 指针都被设置为 NULL 。 二、思路
由于涉及树的层级遍历应该使用深度优先搜索这样可以方便的操作同一层的数据建立一个List用于存放树每层的当前操作节点便于操作其next结点先dfs左子树并将搜索到的数据放入List中此时List的大小即为树的深度且其中的元素即为树的不同深度的最左端点dfs触底为null即返回此时开始检索最底层的右子树层层向上检索每检索到一个结点就将数组中存放的结点next值设置为当前结点并更新数组当前深度的元素为当前结点如此递归至右子树的最右一个null结点为止next都被填充完成
三、解法
解法一
class Solution {private final ListNode NODE_LIST new ArrayList();public Node connect(Node root) {dfs(root, 0);return root;}private void dfs(Node node, Integer depth) {if (node null) {return;}if (depth NODE_LIST.size()) {// 1. 现在的node是最深一层的最左边的结点NODE_LIST.add(node);} else {// 2. 现在的node是最左边结点的next结点NODE_LIST.get(depth).next node;// 3. 更新当前node为node.nextNODE_LIST.set(depth, node);}dfs(node.left, depth 1);dfs(node.right, depth 1);}
}
