迭代插入
<script>class TreeNode {constructor(value) {this.value = value;this.children = [];}
}function insertNode(root, parentValue, newValue) {// 使用栈来辅助遍历let stack = [root];console.log(stack,'stack')// 遍历栈while (stack.length) {// 取出栈顶节点let node = stack.pop();// 检查当前节点是否是目标父节点if (node.value === parentValue) {// 找到目标父节点,插入新节点node.children.push(new TreeNode(newValue));return true; // 插入成功}// 如果不是目标父节点,将其子节点放入栈中for (let child of node.children) {stack.push(child);}}// 遍历完所有节点仍未找到目标父节点return false; // 插入失败
}let root = new TreeNode(1);
root.children.push(new TreeNode(2));
root.children.push(new TreeNode(3));
root.children[0].children.push(new TreeNode(4));
root.children[0].children.push(new TreeNode(5));insertNode(root, 2, 6); // 在值为2的节点下插入值为6的节点</script>
初始化栈:
let stack = [root];
将根节点放入栈中,作为遍历的起点。
遍历栈:
while (stack.length) {let node = stack.pop();// ...
}
每次从栈中取出一个节点,检查是否是目标父节点。
检查目标父节点:
if (node.value === parentValue) {node.children.push(new TreeNode(newValue));return true;
}
如果当前节点的值等于目标父节点的值,将新节点插入到其子节点列表中,并返回 true。
将子节点放入栈中:
for (let child of node.children) {stack.push(child);
}
如果当前节点不是目标父节点,将其所有子节点放入栈中,继续遍历。
遍历结束:
return false;
如果栈为空仍未找到目标父节点,返回 false,表示插入失败。
递归插入
function insertNode(root, parentValue, newValue) {if (root.value === parentValue) {root.children.push(new TreeNode(newValue));return true;}for (let child of root.children) {if (insertNode(child, parentValue, newValue)) {return true;}}return false;
}
迭代查找
function findNode(root, targetValue) {let queue = [root];while (queue.length) {let node = queue.shift();if (node.value === targetValue) {return node;}for (let child of node.children) {queue.push(child);}}return null;
}
递归查找
function findNode(root, targetValue) {if (root.value === targetValue) {return root;}for (let child of root.children) {let result = findNode(child, targetValue);if (result) {return result;}}return null;
}