leetcode-day1- 合并二叉树[617题]
2020-10-10 本文已影响0人
孙静静
坚持一天一道leetcode, 这里将进行个记录~
image.png
leetcode上面默认传入的二叉树，返回的数组
但是我在实现的时候，加入了数组转完全二叉树，和最后的二叉树转成数组的过程。
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Document</title>
</head>
<body>
</body>
<script>
class TreeNode {
constructor(val) {
this.value = val;
this.left = null;
this.right = null;
}
}
/**
* 将数组转成完全二叉树
* 思路： 定义个队列queue，先放入根节点，循环数组，如果没有左节点则添加左节点，反之，有左节点则添加右节点，在右节点结束，去除队列的头部元素（因为完全二叉树是从左到右以此填充节点，符合队列
* 思想，这样当前节点指向队列的头部，这个头部元素一直是新的元素），左右节点添加完成后，判断数组是否有不为null的数，如果有，则继续添加队列，最后返回root（注意：这里一定要返回root）
*/
function arrToTree(arr) { // 将数组转成完全二叉树
let queue = [];
let curr_node = new TreeNode(arr[0]);
let root = null;
root = curr_node;
queue.push(root);
for(let i=1;i<arr.length;i++){
let item = arr[i];
curr_node = queue[0];
let new_node = new TreeNode(item);
if(curr_node.left === null){
curr_node.left = new_node;
} else {
curr_node.right = new_node;
queue.shift();
}
if(item !== null){
queue.push(new_node);
}
}
return root;
}
/**
* 将二叉树转成数组
* 思路： 定义一个队列，将二叉树放入队列中，判断队列是否为空，不为空，则取出队列中的树的value加入数组中，判断是否有左右子树，如果有，则添加队列，以此保证while循环能循环所有的节点
*/
function treeToArr(node){ // 将二叉树转成数组
if(node === null){
return null;
}
let arr = [];
let queue = [];
queue.push(node);
while(queue.length > 0){
let curr_node = queue.shift();
arr.push(curr_node.value);
if(curr_node.left) queue.push(curr_node.left);
if(curr_node.right) queue.push(curr_node.right);
}
return arr;
}
/**
* 617. 合并二叉树
* 题目链接： https://leetcode-cn.com/problems/merge-two-binary-trees/
* 传入的两个参数分别为两棵树，先判断树1和树2是否为空，都不为空，则两则相加
*/
function MergeTwoTree(z1, z2){ // leetcode要求实现的内容
if(z1 === null){
return z2;
}
if(z2 === null){
return z1;
}
z1.value += z2.value;
z1.left = MergeTwoTree(z1.left, z2.left);
z1.right = MergeTwoTree(z1.right, z2.right);
return z1;
}
let arr1 = [1,3,2,5];
let arr2 = [2,1,3,null,4,null,7];
console.log(MergeTwoTree(arrToTree(arr1), arrToTree(arr2)))
console.log(treeToArr(MergeTwoTree(arrToTree(arr1), arrToTree(arr2))))
</script>
</html>
