算法与数据结构-树-简单-合并二叉树

123

标签：href 需要 相加 init 前序遍历 dfs 否则 过程 另一个
合并二叉树

题目

leetcode原题：617. 合并二叉树
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
分析

仔细分析，两棵树需要同步遍历，拿到的每个节点需要根据是否为null进行合并计算。
因为题目中需要生成新的二叉树，所以代码中需要自己new Node，并且需要设置node的左孩子和右孩子，自然而然的想到把递归加到这里，并且递归需要返回节点。
总结一下：

• 整体的框架是一个前序遍历
  
• 递归加入到设置左孩子和右孩子的过程中
  
• 递归的终止过程就是合并计算的过程
  

代码

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public TreeNode mergeTrees(TreeNode t1, TreeNode t2) { return dfs(t1,t2); } private TreeNode dfs(TreeNode t1, TreeNode t2){ if(t1 == null && t2 == null){ return null; } if(t1 == null){ return t2; } if(t2 == null){ return t1; } TreeNode newNode = new TreeNode(t1.val+t2.val); newNode.left = mergeTrees(t1.left,t2.left); newNode.right = mergeTrees(t1.right,t2.right); return newNode; }}算法与数据结构-树-简单-合并二叉树
标签：href 需要 相加 init 前序遍历 dfs 否则 过程 另一个
原文地址：https://www.cnblogs.com/ging/p/14267417.html

那就把他绿了

为了三千积分！

裤兜揣着棒棒糖

发发呆，回回帖，工作结束~

过分迷人

鄙视楼下的顶帖没我快，哈哈

vs小白

LZ敢整点更有创意的不？兄弟们等着围观捏~

吃不饱的大可爱~

这么强,支持楼主，佩服

给朕换尿片

支持支持再支持

不明爬行物

众里寻他千百度，蓦然回首在这里！

专业三秒男

为了三千积分！