每日算法之二叉树中和为某一值的路径(一)(二叉树求和路径)

  本篇文章为你整理了每日算法之二叉树中和为某一值的路径(一)(二叉树求和路径)的详细内容,包含有二叉树和为某一个值的路径 二叉树求和路径 二叉树路径总和 求二叉树结点值之和 每日算法之二叉树中和为某一值的路径(一),希望能帮助你了解 每日算法之二叉树中和为某一值的路径(一)。

   * 描述

   * 给定一个二叉树root和一个值 sum ,判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。

   * 1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点

   * 2.叶子节点是指没有子节点的节点

   * 3.路径只能从父节点到子节点,不能从子节点到父节点

   * 4.总节点数目为n

   * 思路:

   * 既然是检查从根到叶子有没有一条等于目标值的路径,那肯定需要从根节点遍历到叶子,我们可以在根节点每次往下一层的时候,将sum减去节点值,最后检查是否完整等于0. 而遍历的方法我们可以选取二叉树常用的递归前序遍历,因为每次进入一个子节点,更新sum值以后,相当于对子树查找有没有等于新目标值的路径,因此这就是子问题,递归的三段式为:

   * 终止条件: 每当遇到节点为空,意味着过了叶子节点,返回。每当检查到某个节点没有子节点,它就是叶子节点,此时sum减去叶子节点值刚好为0,说明找到了路径。

   * 返回值: 将子问题中是否有符合新目标值的路径层层往上返回。

   public boolean hasPathSum(TreeNode root, int sum) {

   // write code here

   if (root == null) return false;

   if (root.left == null root.right == null sum - root.val == 0) return true;

   return hasPathSum(root.left, sum - root.val) hasPathSum(root.right, sum - root.val);

   * 描述

   * 求给定二叉树的最大深度,

   * 深度是指树的根节点到任一叶子节点路径上节点的数量。

   * 最大深度是所有叶子节点的深度的最大值。

   * (注:叶子节点是指没有子节点的节点。)

   * @param root

   * @return

   public int maxDepth (TreeNode root) {

   // write code here

   if (root == null) return 0;

   return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;

   public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {

   // write code here

   * 思路:

   * 要将一棵二叉树的节点与另一棵二叉树相加合并,肯定需要遍历两棵二叉树,那我们可以考虑同步遍历两棵二叉树,这样就可以将每次遍历到的值相加在一起。遍历的方式有多种,这里推荐前序递归遍历。

   * 集体做法

   * step 1:首先判断t1与t2是否为空,若为则用另一个代替,若都为空,返回的值也是空。

   * step 2:然后依据前序遍历的特点,优先访问根节点,将两个根点的值相加创建到新树中。

   * step 3:两棵树再依次同步进入左子树和右子树。

   if (t1 == null t2 == null) return t1 == null ? t2 : t1;

   TreeNode treeNode = new TreeNode();

   treeNode.val = t1.val + t2.val;

   treeNode.left = mergeTrees(t1.left, t2.left);

   treeNode.right = mergeTrees(t1.right, t2.right);

   return treeNode;

  

 

 

  以上就是每日算法之二叉树中和为某一值的路径(一)(二叉树求和路径)的详细内容,想要了解更多 每日算法之二叉树中和为某一值的路径(一)的内容,请持续关注盛行IT软件开发工作室。

郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。

留言与评论(共有 条评论)
   
验证码: