二叉树 - 合并二叉树

2024-09-06 03:12

文章标签 二叉树合并

本文主要是介绍二叉树 - 合并二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

617. 合并二叉树

在这里插入图片描述

方法一：递归

/*** Definition for a binary tree node.* function TreeNode(val, left, right) {*     this.val = (val===undefined ? 0 : val)*     this.left = (left===undefined ? null : left)*     this.right = (right===undefined ? null : right)* }*/
/*** @param {TreeNode} root1* @param {TreeNode} root2* @return {TreeNode}*/
var mergeTrees = function (root1, root2) {const preOrder = (root1, root2) => {if (!root1) {return root2;}if (!root2) {return root1;}root1.val += root2.val;root1.left = preOrder(root1.left, root2.left);root1.right = preOrder(root1.right, root2.right);return root1;}return preOrder(root1, root2);
}

方法二：迭代

/*** Definition for a binary tree node.* function TreeNode(val, left, right) {*     this.val = (val===undefined ? 0 : val)*     this.left = (left===undefined ? null : left)*     this.right = (right===undefined ? null : right)* }*/
/*** @param {TreeNode} root1* @param {TreeNode} root2* @return {TreeNode}*/
var mergeTrees = function (root1, root2) {if (root1 === null) return root2;if (root2 === null) return root1;let queue = [];queue.push(root1);queue.push(root2);while (queue.length) {let node1 = queue.shift();let node2 = queue.shift();node1.val += node2.val;if (node1.left!== null && node2.left!== null) {queue.push(node1.left);queue.push(node2.left);}if (node1.right!== null && node2.right!== null) {queue.push(node1.right);queue.push(node2.right);}if (node1.left === null && node2.left!== null) {node1.left = node2.left;}if (node1.right === null && node2.right!== null) {node1.right = node2.right;}}return root1;
};