console.log 二叉树中子树的节点和为偶数

Question

以下是我正在处理的编码挑战。

You are given a binary tree in which each node contains a value. Design an algorithm to print all nodes whose subtree adds up to an even number.

这是我用于测试的树，以及我的函数：

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

const a = new Node(3);
const b = new Node(11);
const c = new Node(4);
const d = new Node(4);
const e = new Node(-2);
const f = new Node(2);

a.left = b;
a.right = c;
b.left = d;
b.right = e;
c.right = f;

//       3
//    /    \
//   11     4
//  / \      \
// 4   -2     2

const isEven = (node) => {
  if (node === null) return 0;
  let left = isEven(node.left);
  let right = isEven(node.right);
  let sum = left + right + node.val;
  if (sum % 2 === 0) {
    console.log(node.val);
  }
  return;
};

console.log(isEven(a));

该功能未按我希望的方式运行。

鉴于这棵树，我认为正确的输出应该是：3、4、-2、4 又名 a、d、e 和 c。（假设空 = 0）但我得到的输出是：4, -2, 2, undefined

~~我什至不确定 2 是从哪里来的，因为没有节点等于 2。~~（这是我的错误）

Answer 1

您可以使函数 return 成为子树求和。然后，将左右子节点调用函数的结果和节点自身的值相加，得到以该节点为根的子树之和。

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

const a = new Node(3);
const b = new Node(11);
const c = new Node(4);
const d = new Node(4);
const e = new Node(-2);
const f = new Node(2);

a.left = b;
a.right = c;
b.left = d;
b.right = e;
c.right = f;

const checkEven = node => {
  if(!node) return 0;
  const sum = node.val + checkEven(node.left) + checkEven(node.right);
  if(sum % 2 === 0) console.log(node.val);
  return sum;
}
checkEven(a);

Answer 2

the output I'm getting is: 4, -2, 2, undefined.

你最后得到 undefined 的原因是你执行了主 isEven 调用的 console.log，但是你的 isEven 函数 return没什么：它的最后一条指令是 return，所以主 console.log 输出 undefined。实际上，您不应该在主程序中执行 console.log，因为节点的打印已经在您的函数中处理了。

I'm not sure where the 2 is even coming from because no node is equal to 2.

节点f的值为2，应该在输出中。

I think the correct output should be: 3, 4, -2, 4 aka a, d, e and c. (assuming null = 0)

... 和 f.

您没有得到所有结果，因为 isEven 只能 return null 或 undefined，因此 left + right 不会给出您期望的结果: 将 null 添加到数字会将 null 视为 0，但是当涉及 undefined 时，表达式将计算为 NaN.

这通过将最后的 return 更改为 return sum 来解决。

这是经过这两项更正的脚本：

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

const a = new Node(3);
const b = new Node(11);
const c = new Node(4);
const d = new Node(4);
const e = new Node(-2);
const f = new Node(2);

a.left = b;
a.right = c;
b.left = d;
b.right = e;
c.right = f;

//       3
//    /    \
//   11     4
//  / \      \
// 4   -2     2

const isEven = (node) => {
  if (node === null) return 0;
  let left = isEven(node.left);
  let right = isEven(node.right);
  let sum = left + right + node.val;
  if (sum % 2 === 0) {
    console.log(node.val);
  }
  return sum; // <-- sum!
};

isEven(a); // <-- no console.log

替代树构造

与您的问题无关，但您可以通过定义用于指定 left 和 right 引用的参数来使您的 Node 构造函数更加灵活。然后你可以在一个嵌套表达式中构建树。

class Node {
  constructor(val, left=null, right=null) {  // <-- extra parameters
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

const a = new Node(3,
    new Node(11,
        new Node(4),
        new Node(-2)
    ),
    new Node(4,
        null,
        new Node(2)
    )
);

const isEven = (node) => {
  if (node === null) return 0;
  let left = isEven(node.left);
  let right = isEven(node.right);
  let sum = left + right + node.val;
  if (sum % 2 === 0) {
    console.log(node.val);
  }
  return sum;
};

isEven(a);

console.log 二叉树中子树的节点和为偶数

console.log Nodes in a Binary Tree who’s subtrees have Even sum

javascript

algorithm

binary

tree

data-structures

替代树构造