美文网首页
计算二叉树叶子节点之和

计算二叉树叶子节点之和

作者: 大小姐_ | 来源:发表于2020-11-02 16:30 被阅读0次

给定一颗二叉树,从根节点到叶子节点组成一个数,计算一颗二叉树所有叶子节点之和

leetcode 地址:
https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/

自己的解法:

先获取叶子节点的每一个遍历的数字为数组,再对其求和
没有想到可以利用每一个节点的数字为上一个节点数字10再加上当前值*

function (root){
  let stackPtr =[];
  let stackArr = []
  let ptr = root;
  let bianli = []
  let result = []
  while(ptr){
    bianli.push(ptr.val)
    if(ptr.right){
      stackPtr.push(ptr.right)
      stackArr.push(bianli)
    }
    if(ptr.left){
      ptr = ptr.left
    }else{
      ptr = stackPtr.pop()
      if(!ptr.right) result.push([...stackArr.pop()))
    }
  }
return result.reduce((pre,cur)=>{
  return pre+=Number(cur.join(''))
  },0)
}

太复杂了

官方解法

深度遍历

如果一个节点是叶子节点,所代表的值为前一个节点的值*10加上当前值
如果一个节点有左右节点,则对其左右节点值相加即为当前节点的值

var sumNumbers =  (root)=>{
    var tree = (root,sum)=>{
        if(!root)return 0
        sum = sum*10+root.val
        if(!root.left&&!root.right){
            return sum
        }else {
            return tree(root.right,sum)+tree(root.left,sum)
        }
    }
    return tree(root,0)

}

广度遍历

对求和和当前节点建立两个队列
对叶子节点,则直接返回队首的求和值
有左右节点,前一个值*10+当前值放入队列中

var sumNumbers =  (root)=>{
    if(!root)return 0
    var stackNum = []
    var stackPtr = []
    stackNum.push(root.val)
    stackPtr.push(root)
    let result = 0
    while(stackPtr.length){
        var nodePtr = stackPtr.shift()
        var nodeNum = stackNum.shift()
        if(!nodePtr.right&&!nodePtr.left){
            result+=nodeNum
        }
         if(nodePtr.left){
            stackPtr.push(nodePtr.left)
            stackNum.push(nodeNum*10+nodePtr.left.val)
        }
         if(nodePtr.right){
            stackPtr.push(nodePtr.right)
            stackNum.push(nodeNum*10+nodePtr.right.val)
        }
    }
    return result

}

相关文章

  • 计算二叉树叶子节点之和

    给定一颗二叉树,从根节点到叶子节点组成一个数,计算一颗二叉树所有叶子节点之和 leetcode 地址:https:...

  • 404. 左叶子之和

    计算给定二叉树的所有左叶子之和。 解:1代表左节点,0代表右节点

  • 2019-03-27 待提高

    1.#### 左叶子之和 计算给定二叉树的所有左叶子之和。 示例: / 9 20/ 15 7 在这个二叉树...

  • 左叶子之和

    左叶子之和,给定二叉树的根节点 root ,返回所有左叶子之和。 输入: root = [3,9,20,null,...

  • 二叉树

    计算一颗二叉树中的叶子节点数 一棵树的叶子节点数目等于他的左子树叶子数加上右子树叶子数之和;而当一个节点没有左子树...

  • LeetCode:404. 左叶子之和

    计算给定二叉树的所有左叶子之和。 示例: 方法一: 思想:把所有节点都当作根节点。递归处理 方法二 参考更简单的递归方法

  • 404-左叶子之和

    左叶子之和 题目 计算给定二叉树的所有左叶子之和。 示例: 在这个二叉树中,有两个左叶子,分别是 9 和 15,所...

  • 2021-12-16 404. 左叶子之和【Easy】

    计算给定二叉树的所有左叶子之和。 示例: 方法一:

  • 563. 二叉树的坡度

    给定一个二叉树,计算 整个树 的坡度 。 一个树的 节点的坡度 定义即为,该节点左子树的节点之和和右子树节点之和的...

  • 【404】 二叉树所有的左叶子之和

    题目:计算给定二叉树的所有左叶子之和。 二叉树遍历一般用递归来解决,主要是找到递归结束的点,本次左叶子之和=右子树...

网友评论

      本文标题:计算二叉树叶子节点之和

      本文链接:https://www.haomeiwen.com/subject/otnrvktx.html