js 对比两个tree,找出发生改变的节点并返回
时间: 2024-02-16 09:03:44 浏览: 20
可以使用深度优先搜索(DFS)来对比两棵树:
1. 首先比较根节点,如果不同则返回根节点。
2. 然后递归比较左子树和右子树,如果左子树或右子树中有一个不同,则返回该子树的根节点。
3. 如果左子树和右子树都相同,则返回 null。
代码实现如下:
```javascript
function compareTrees(tree1, tree2) {
if (!tree1 && !tree2) {
return null; // 两棵树都为空,返回 null
}
if (!tree1 || !tree2 || tree1.value !== tree2.value) {
return tree1; // 根节点不同或有一棵树为空,返回根节点
}
// 递归比较左子树和右子树
const left = compareTrees(tree1.left, tree2.left);
const right = compareTrees(tree1.right, tree2.right);
if (left || right) {
return left || right;
}
return null;
}
```
调用函数:
```javascript
const tree1 = {
value: 1,
left: {
value: 2,
left: { value: 4 },
right: { value: 5 }
},
right: {
value: 3,
left: { value: 6 },
right: { value: 7 }
}
};
const tree2 = {
value: 1,
left: {
value: 2,
left: { value: 4 },
right: { value: 8 } // 改变了节点 5 的值
},
right: {
value: 3,
left: { value: 6 },
right: { value: 7 }
}
};
const changedNode = compareTrees(tree1, tree2);
console.log(changedNode); // { value: 5 }
```
以上代码中,我们对比了两棵树 `tree1` 和 `tree2`,发现节点 `5` 的值改变了,所以返回了该节点。