深度优先遍历 DFS
解题思路
中序遍历两棵树，并将结果存储到两个 list 里面；
利用双指针，对两个有序 list 进行合并；
复杂度
-
时间复杂度：
O(n+m)，其中 n 和 m 分别为两棵二叉搜索树的节点个数； -
空间复杂度：
O(n+m)，存储数组以及递归时的栈空间均为O(n+m)；
实现代码
var getAllElements = function (root1, root2) {
// 1. 中序遍历两棵树，并将结果存储起来
const nums1 = [];
const nums2 = [];
const inorder = (node, res) => {
if (node) {
inorder(node.left, res);
res.push(node.val);
inorder(node.right, res);
}
};
inorder(root1, nums1);
inorder(root2, nums2);
// 2. 合并两个有序数组
const merged = [];
let p1 = 0, p2 = 0;
while (true) {
if (p1 === nums1.length) {
merged.push(...nums2.slice(p2));
break;
}
if (p2 === nums2.length) {
merged.push(...nums1.slice(p1));
break;
}
merged.push(nums1[p1] < nums2[p2] ? nums1[p1++] : nums2[p2++]);
}
return merged;
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 234. 回文链表
上一篇
评论
