赞
踩
root
和两个整数 val
和 depth
,在给定的深度 depth
处添加一个值为 val
的节点行。root
位于深度 1
。depth
,对于深度为 depth - 1
的每个非空树节点 cur
,创建两个值为 val
的树节点作为 cur
的左子树根和右子树根。cur
原来的左子树应该是新的左子树根的左子树。cur
原来的右子树应该是新的右子树根的右子树。depth == 1
意味着 depth - 1
根本没有深度,那么创建一个树节点,值 val
作为整个原始树的新根,而原始树就是新根的左子树。示例 1:
示例 2:
/** * 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 TreeNode addOneRow(TreeNode root, int val, int depth) { // 边界条件 if (depth == 1) { return new TreeNode(val, root, null); } // 保存当前层节点 List<TreeNode> curLevel = new ArrayList<TreeNode>(); curLevel.add(root); // 使用广度优先搜索要插入行的上一行 for (int i = 1; i < depth - 1; i++) { List<TreeNode> temp = new ArrayList<TreeNode>(); for (TreeNode node : curLevel) { if (node.left != null) { temp.add(node.left); } if (node.right != null) { temp.add(node.right); } } curLevel = temp; } // 插入目标行 for (TreeNode node : curLevel) { node.left = new TreeNode(val, node.left, null); node.right = new TreeNode(val, null, node.right); } // 返回结果 return root; } }
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def addOneRow(self, root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]: # 边界条件 if root == None: return if depth == 1: return TreeNode(val, root, None) # 保存当前层节点 cur_level = [root] # 使用广度优先搜索要插入行的上一行 for _ in range(1, depth - 1): temp = [] for node in cur_level: if node.left: temp.append(node.left) if node.right: temp.append(node.right) cur_level = temp # 插入目标行 for node in cur_level: node.left = TreeNode(val, node.left, None) node.right = TreeNode(val, None, node.right) # 返回结果 return root
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ struct TreeNode* addOneRow(struct TreeNode* root, int val, int depth) { // 边界条件 if (root == NULL) { struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode)); node->val = val; node->left = NULL; node->right = NULL; return node; } if (depth == 1) { struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode)); node->val = val; node->left = root; node->right = NULL; return node; } // 初始化队列 struct TreeNode** queue = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * 10001); int front = 0; int rear = 0; queue[rear++] = root; // 存储树高 int level = 1; // 使用广度优先搜索算法插入目标节点 while (front != rear) { // 当前层节点数量 int size = rear - front; // 如果找到目标行,直接插入目标节点即可 if (level == depth - 1) { for (int i = 0; i < size; i++) { struct TreeNode* node = queue[front++]; struct TreeNode* nodeLeft = (struct TreeNode*)malloc(sizeof(struct TreeNode)); nodeLeft->val = val; nodeLeft->left = node->left; nodeLeft->right = NULL; node->left = nodeLeft; struct TreeNode* nodeRight = (struct TreeNode*)malloc(sizeof(struct TreeNode)); nodeRight->val = val; nodeRight->left = NULL; nodeRight->right = node->right; node->right = nodeRight; } break; } // 处理当前层的节点,并将下一层的节点加入队列 for (int i = 0; i < size; i++) { struct TreeNode* node = queue[front++]; if (node->left != NULL) { queue[rear++] = node->left; } if (node->right != NULL) { queue[rear++] = node->right; } } // 获取二叉树的层数 level++; } // 释放内存 free(queue); // 返回结果 return root; }
Java语言版
C语言版
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。