已知两颗二叉树,将它们合并成一颗二叉树。合并规则是:都存在的结点,就将结点值加起来,否则空的位置就由另一个树的结点来代替。例如:
两颗二叉树是:
Tree 1
两颗二叉树是:
Tree 1
Tree 2
合并后的树为
数据范围:树上节点数量满足 ,树上节点的值一定在32位整型范围内。
进阶:空间复杂度 ,时间复杂度
{1,3,2,5},{2,1,3,#,4,#,7}
{3,4,5,5,4,#,7}
如题面图
{1},{}
{1}
public class Solution { /** * * @param t1 TreeNode类 * @param t2 TreeNode类 * @return TreeNode类 */ public TreeNode mergeTrees(TreeNode t1, TreeNode t2) { f(t1, null, t2, null); return t1; } void f(TreeNode t1Ch, TreeNode parent1, TreeNode t2Ch, TreeNode parent2) { if (t1Ch == null && t2Ch == null) return; if (t1Ch == null) { if (parent1.left == t1Ch&&t2Ch==parent2.left) parent1.left = t2Ch; else { parent1.right = t2Ch; } return; } if (t2Ch != null) { t1Ch.val = t1Ch.val + t2Ch.val; }else { return; } f(t1Ch.left, t1Ch, t2Ch.left, t2Ch); f(t1Ch.right, t1Ch, t2Ch.right, t2Ch); } }
class Solution { public: /** * * @param t1 TreeNode类 * @param t2 TreeNode类 * @return TreeNode类 */ TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) { // write code here if(!t1 && !t2) return nullptr; if(!t1) return t2; if(!t2) return t1; t1->val += t2->val; t1->left = mergeTrees(t1->left, t2->left); t1->right = mergeTrees(t1->right, t2->right); return t1; } };
public class Solution { /** * * @param t1 TreeNode类 * @param t2 TreeNode类 * @return TreeNode类 */ public TreeNode mergeTrees (TreeNode t1, TreeNode t2) { if (t1 == null && t2 == null) return null; if (t1 == null || t2 == null) return t1 == null ? t2 : t1; // 此时 t1、t2 均不为 null // 合并节点的值 t1.val = t1.val + t2.val; // 合并左子树 t1.left = mergeTrees(t1.left, t2.left); // 合并右子树 t1.right = mergeTrees(t1.right, t2.right); return t1; } }
struct TreeNode* mergeTrees(struct TreeNode* t1, struct TreeNode* t2) { if (!t1 || !t2) return t1 ? t1 : t2; t1->val += t2->val; t1->left = mergeTrees(t1->left, t2->left); t1->right = mergeTrees(t1->right, t2->right); return t1; }
class Solution { public: TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) { if (t1 && t2) { t1->val += t2->val; t1->left = mergeTrees(t1->left, t2->left); t1->right = mergeTrees(t1->right, t2->right); return t1; } return t1 ? t1 : t2; } };
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Solution { /** * * @param t1 TreeNode类 * @param t2 TreeNode类 * @return TreeNode类 */ public TreeNode mergeTrees (TreeNode t1, TreeNode t2) { // write code here if(t1 != null && t2 != null){ t2.val += t1.val; t2.left = mergeTrees(t1.left, t2.left); t2.right = mergeTrees(t1.right, t2.right); } return t2 == null ? t1 : t2; } }
struct TreeNode* mergeTrees(struct TreeNode* t1, struct TreeNode* t2 ) { // write code here if(!t1||!t2) return t1?t1:t2;//比较那棵二叉树的子树不为空 t1->val+=t2->val;//存在的结点的值相加 t1->left=mergeTrees(t1->left,t2->left);//接收返回更长的左子树 t1->right=mergeTrees(t1->right,t2->right);//接收返回更长的右子树 return t1; }
class Solution { public: /** * * @param t1 TreeNode类 * @param t2 TreeNode类 * @return TreeNode类 */ TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) { // write code here if(t1 == nullptr) return t2; if(t2 == nullptr) return t1; TreeNode* head = t1; stack<TreeNode*> st1; stack<TreeNode*> st2; while(!st1.empty()||t1!=nullptr) { while(t1!= nullptr&&t2!= nullptr) { st1.push(t1); st2.push(t2); t1=t1->left; t2=t2->left; } if(t2 != nullptr ) { t1 = st1.top(); t1->left =t2; } t1 = st1.top(); st1.pop(); t2 = st2.top(); st2.pop(); t1->val += t2->val; if(t1->right==nullptr || t2->right == nullptr) { if(t1->right == nullptr) { t1->right = t2->right; } t1 = nullptr; t2 = nullptr; }else { t1 = t1->right; t2 = t2->right; } } return head; } };
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * * @param t1 TreeNode类 * @param t2 TreeNode类 * @return TreeNode类 */ TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) { if (t1 == nullptr && t2 == nullptr) return nullptr; if (t1 == nullptr && t2 != nullptr) return t2; if (t2 == nullptr && t1 != nullptr) return t1; t1->val += t2->val; t1->left = mergeTrees(t1->left, t2->left); t1->right = mergeTrees(t1->right, t2->right); return t1; } };
# class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param t1 TreeNode类 # @param t2 TreeNode类 # @return TreeNode类 # class Solution: def mergeTrees(self , t1: TreeNode, t2: TreeNode) -> TreeNode: # write code here if not t1: return t2 if not t2: return t1 head = TreeNode(t1.val + t2.val) head.left, head.right = self.mergeTrees(t1.left, t2.left), self.mergeTrees(t1.right, t2.right) return head
struct TreeNode* mergeTrees(struct TreeNode* t1, struct TreeNode* t2 ) { // write code here //若t1不存在或都不存在,返回t2 if(!t1||!t2) { return t1?t1:t2; } //相同位置结点值相加 t1->val+=t2->val; //遍历左子树 t1->left=mergeTrees(t1->left,t2->left); //遍历右子树 t1->right=mergeTrees(t1->right,t2->right); //t2移入t1 return t1; }
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param t1 TreeNode类 * @param t2 TreeNode类 * @return TreeNode类 */ TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) { // write code here if (t1 == NULL) { return t2; } else if (t2 == NULL) { return t1; } else { TreeNode* ret = NULL; vector<pair<TreeNode*, bool>> st1; vector<pair<TreeNode*, bool>> st2; TreeNode* p1 = t1; TreeNode* p2 = t2; while (true) { if (p1 != NULL) { if (p2 != NULL) { p1->val += p2->val; st1.push_back(make_pair(p1, false)); st2.push_back(make_pair(p2, false)); p1 = p1->left; p2 = p2->left; } else { if (st2.back().second) { st2.pop_back(); p2 = NULL; st1.pop_back(); p1 = NULL; } else { st2.back().second = true; p2 = st2.back().first->right; st1.back().second = true; p1 = st1.back().first->right; } } } else { if (p2 != NULL) { if (st2.back().second) { st2.back().first->right = NULL; st1.back().second = true; st1.back().first->right = p2; } else { st2.back().first->left = NULL; st1.back().second = false; st1.back().first->left = p2; } p2 = NULL; p1 = NULL; } else { if (st2.back().second) { st2.pop_back(); p2 = NULL; st1.pop_back(); p1 = NULL; } else { st2.back().second = true; p2 = st2.back().first->right; st1.back().second = true; p1 = st1.back().first->right; } } } if (st1.empty() && p1 == NULL && st2.empty() && p2 == NULL) { break; } } if (st1.empty() && p1 == NULL && st2.empty() && p2 == NULL) { ret = t1; } return ret; } } };
# class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param t1 TreeNode类 # @param t2 TreeNode类 # @return TreeNode类 # class Solution: def mergeTrees(self , t1: TreeNode, t2: TreeNode) -> TreeNode: # write code here if not t1: return t2 if not t2: return t1 merged = TreeNode(t1.val + t2.val) merged.left = self.mergeTrees(t1.left, t2.left) merged.right = self.mergeTrees(t1.right, t2.right) return merged
class Solution { public: /** * * @param t1 TreeNode类 * @param t2 TreeNode类 * @return TreeNode类 */ TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) { if (t1 == nullptr) { return t2; } if (t2 == nullptr) { return t1; } auto* mergedNode = new TreeNode(t1->val + t2->val); mergedNode->left = mergeTrees(t1->left, t2->left); mergedNode->right = mergeTrees(t1->right, t2->right); return mergedNode; } };
public TreeNode mergeTrees (TreeNode t1, TreeNode t2) { // write code here if (t1 == null && t2 == null) return null; if (t1 == null) return t2; if (t2 == null) return t1; TreeNode head = new TreeNode(t1.val + t2.val); head.left = mergeTrees(t1.left,t2.left); head.right = mergeTrees(t1.right,t2.right); return head; }
public class Solution { /** * * @param t1 TreeNode类 * @param t2 TreeNode类 * @return TreeNode类 */ public TreeNode mergeTrees (TreeNode t1, TreeNode t2) { // 两个节点都为null,则没必要继续比较,直接返回null if(t1 == null && t2 == null) return null; // 拿到两个节点的值之和 int num = (t1 != null ? t1.val : 0) + (t2 != null ? t2.val : 0); if(t1 == null){ // t1等于null时,创建一个对象 存储之和 t1 = new TreeNode(num); }else{ // 否则替换 val t1.val = num; } // 然后继续左子树递归遍历 // 因为将t2 合并到 t1里,所以当递归拿到返回值以后,重新赋值给t1.left t1.left = mergeTrees(t1.left, t2 == null ? null : t2.left); // 然后继续右子树递归遍历 // 因为将t2 合并到 t1里,所以当递归拿到返回值以后,重新赋值给t1.right t1.right = mergeTrees (t1.right, t2 == null ? null : t2.right); // 返回合并结果后的t1 return t1; } }