javascript 在二叉树中找到所有的叶子并将它们相加到它们的父亲

yv5phkfx 于 2022-11-20 发布在 Java

关注(0)|答案(2)|浏览(175)

我真的在纠结一个问题：我必须找到二叉树中的所有叶子，并使用递归和基本控制（没有专门的函数）将它们相加到它们的父亲。
我试着检查所有节点的子节点，看看它们是否是叶节点，然后将它们添加到它们的父节点，但似乎无法正确完成递归

t = { val: 1, sx: { val: 8, sx: { val: 7, sx: {}, dx: {} }, dx: { val: 

1, sx: {}, dx: {} } }, dx: { val: 3, sx: { val: 5, sx: {}, dx: {} }, dx: {} } };

function pota3(t) {
  if (t == null) { return }

  if (t.dx != null) {
    if (t.dx.sx == null && t.dx.dx == null) {
      t.val += t.dx.val
        delete t.dx 
    }
  }
  if (t.sx != null) {
    if (t.sx.sx == null && t.sx.dx == null) {
      t.val += t.sx.val
        delete t.sx 
    }
  }
  pota3(t.dx)
  pota3(t.sx)
}
pota3(t)

期望结果：

t = {
  val: 1,
  sx: { val: 16,sx: {}, dx: {}},
  dx: { val: 8, sx: {}, dx:{} }
  }

JavaScript

来源：https://stackoverflow.com/questions/74501151/finding-all-the-leafs-in-a-binary-tree-and-summing-them-to-their-fathers

2条答案

按热度按时间

dwthyt8l1#

const t = { val: 1, sx: { val: 8, sx: { val: 7, sx: {}, dx: {} }, dx: { val: 
1, sx: {}, dx: {} } }, dx: { val: 3, sx: { val: 5, sx: {}, dx: {} }, dx: {} } };

console.log(t);

const addLeafs = (point) => {
  if(point.sx.val !== undefined || point.dx.val !== undefined) {
    // not a leaf
    if(point.sx.val !== undefined) {
      // try to add first child value if it's not empty
      const adding = addLeafs(point.sx);
      if(adding > 0) {
        point.val += adding;
        point.sx = {};
      }
    }
    if(point.dx.val !== undefined) {
      // try to add second child if it's not empty
      const adding = addLeafs(point.dx);
      if(adding > 0) {
        point.val += adding;
        point.dx = {};
      }
    }
    // it's not a leaf, so parent should not increase value
    return 0;
  } else {
    // it's a leaf - add it's value to parent
    return point.val;
  }
}

addLeafs(t);
console.log(t);

赞(0）回复(0）举报 2022-11-20

yhqotfr82#

您可以定义一些退出条件，例如没有节点或没有val属性，并指定val和所有其他子节点。
第一个

赞(0）回复(0）举报 2022-11-20