一天一大 lee(左叶子之和)难度:简单-Day20200919

前端小书童

发布于 2020-09-24 14:35:10

2630

发布于 2020-09-24 14:35:10

文章被收录于专栏：前端小书童

题目:[1]

计算给定二叉树的所有左叶子之和。

示例：

    3
   / \
  9  20
    /  \
   15   7

在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

抛砖引玉

抛砖引玉

二叉树遍历，首先想到的有两种遍历方式深度优先搜索(DFS)、广度优先搜索(BFS)

剩下的问题就是在遍历中找出哪些节点是左叶子节点了：

叶子结点：没有下一层（即该节点之后没有left和right）
左叶子结点：节点上一次被其他节点（设为node）left连接

那么在判断出左叶子节点的逻辑应该在node那一层就完成（因为二叉树是没有办法回溯到上一个节点的）

满足下面两个条件说明就是左叶子节点，传入节点node：

node的左节点，其left和right均为null

深度优先搜索(DFS)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumOfLeftLeaves = function(root) {
  let _result = 0;
  if(root === null) return _result;
  function dfs(node){
    // 终止条件，遇到叶子结点
    if(node === null) return
    let left = node.left,
        right = node.right
    // node的左节点，其left和right均为null
    if(left != null &&left.left == null && left.right == null){
        _result = _result + left.val
    }
    // 继续遍历子树
    dfs(left)
    dfs(right)
  }
  dfs(root)
  return _result
};

优化：

在上面的逻辑中，发现有的递归时可以省略的，也没有利用起来递归的返回值：

已经查到了node子树的左叶子节点，node的left子树还是要参与下一层递归
可以不声明结果变量然后向其累加，可以利用递归返回值累加

var sumOfLeftLeaves = function (root) {
  if (!root) return 0
  if (isLeaf(root.left)) {
    // 是左叶子节点则相加
    return root.left.val + sumOfLeftLeaves(root.right)
  }
  // 不是点则再往下查
  return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right)

};
function isLeaf(node) {
  // 判断此节点存在
  if (node === null) return false
  // 判断此节点是否为叶子节点
  return node.left === null && node.right === null
}

广度优先搜索(BFS)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumOfLeftLeaves = function(root) {
  let _result = 0,
      quene = [root];
  if(root === null) return _result;
  while(quene.length){
    let node = quene.shift()
    // 终止条件，遇到叶子结点
    if(node === null) continue
    let left = node.left;
    // node的左节点，其left和right均为null
    if(left != null &&left.left === null && left.right === null){
      _result = _result + left.val
    }
    // 子树继续入栈待遍历
    quene.push(left)
    quene.push(node.right)
  }
  return _result
};

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-09-19，如有侵权请联系 cloudcommunity@tencent.com 删除

node.js