console.log二叉樹中的節點，其子樹的總和為偶數

以下是我正在處理的編碼挑戰。

給定一個二叉樹，其中每個節點都包含一個值。設計一個演算法來列印所有子樹加起來為偶數的所有節點。

這是我用于測驗的樹，以及我的函式：

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 aka a, d, e 和 c。（假設 null = 0）但我得到的輸出是：4, -2, 2, undefined

我不確定 2 來自哪里，因為沒有節點等于 2。（這是我的錯誤）任何幫助將不勝感激，謝謝。

uj5u.com熱心網友回復：

您可以使函式回傳子樹總和。然后，將左右孩子的函式呼叫結果和節點本身的值相加，得到以該節點為根的子樹的總和。

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);

uj5u.com熱心網友回復：

我得到的輸出是：4, -2, 2, undefined。

你最后得到的原因undefined是你做了一個console.log主isEven呼叫，但你的isEven函式什么都不回傳：它的最后一條指令是return，所以主console.log輸出是undefined。實際上，您不應該console.log在主程式中執行 a ，因為節點的列印已經在您的函式中進行了處理。

我不確定 2 來自哪里，因為沒有節點等于 2。

Nodef的值為 2，它應該在輸出中。

我認為正確的輸出應該是：3, 4, -2, 4 aka a, d, e 和 c。（假設 null = 0）

... 和f.

您沒有得到所有結果，因為isEven只能回傳nullor 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);

標籤：javascript 算法 数据结构 树 二进制

上一篇：用于排序的重新洗牌次數

下一篇：理解像素在螢屏上的顯示