【两颗二叉树】【递归遍历】【▲队列层序遍历】Leetcode 617. 合并二叉树

- 解法1 深度优先递归前序
- 解法2 采用队列进行层序遍历挺巧妙的可以再看

在这里插入图片描述

---------------🎈🎈题目链接🎈🎈-------------------

解法1 深度优先递归前序

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if(root1==null) return root2;if(root2==null) return root1;TreeNode root = new TreeNode(root1.val+root2.val);root.left = mergeTrees(root1.left,root2.left);  root.right = mergeTrees(root1.right,root2.right);return root;}
}

解法2 采用队列进行层序遍历挺巧妙的可以再看

在temp1 的基础上改改好了返回


class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {Queue<TreeNode> myqueue = new LinkedList<>();if(root1 == null) return root2;if(root2 == null) return root1;myqueue.add(root1);myqueue.add(root2);while(!myqueue.isEmpty()){TreeNode temp1 = myqueue.poll();TreeNode temp2 = myqueue.poll();temp1.val = temp1.val+temp2.val;if(temp1.left!=null && temp2.left!= null){ // 如果两棵树左节点都不为空，加入队列myqueue.add(temp1.left);myqueue.add(temp2.left);}if(temp1.right!=null && temp2.right!= null){ // 如果两棵树左节点都不为空，加入队列myqueue.add(temp1.right);myqueue.add(temp2.right);}if(temp1.left==null){ // 如果temp1的左节点为空，直接赋值temp2.lefttemp1.left = temp2.left;}if(temp1.right==null){ // 如果temp1的右节点为空，直接赋值temp2.righttemp1.right = temp2.right;}}return root1;}
}