javascript - 在 JavaScript 中检查二叉树是否对称

Question

给定一棵树，我应该检查它是否是对称的，或者它是否在中心有一面镜子。我遗漏了一个边缘案例，我终其一生都无法弄清楚它是什么。我在 CodeFights 上遇到的唯一错误是“超出输出限制”

Here's what the example tree looks like

这是主要函数 isTreeSymmetric 将其左分支分配给调用 leftBranch 函数的变量，并将右分支分配给 rightBranch 函数递归返回一个数组。

我使用两个不同函数的原因是因为它帮助我划分了我的思维，因为在树的左半部分我必须从右到左，而在右半部分则相反，这样我就不会迷路树洞。

isTreeSymmetrical 中的最后一个 return 语句然后检查返回的类型值是否为数组，后跟一个三元组，该三元组检查左右数组或在值不是数组的情况下检查变量 lb 和 rb 是否相等。

我一直在为此努力，感觉就像永恒一样!请帮忙。

function isTreeSymmetric(t) {
  "use strict";
  if(!t || ( (!t.left && !t.right) && t.value)) return true
  if(!t.left || !t.right) return false

  let left = t.left, right = t.right
  let rb = rightBranch(right), lb = leftBranch(left)
    console.log(`right branch values are ${rb} | left branch values are ${lb}`)
    return Array.isArray( rb || lb ) ?
              rb.every( (e, i) => e === lb[i]) :
                lb === rb

}


//ON RIGHT BRANCH RETURN CHILDREN LEFT TO RIGHT
function rightBranch(n){
  "use strict";
  if(!n) return null

  let value = n.value
  if(!n.left && !n.right) return value

  let left = n.left || null, right = n.right || null;

  return [value].concat(
    rightBranch(left),
    rightBranch(right)
  )

}

// ON LEFT BRANCH RETURN CHILDREN RIGHT TO LEFT
function leftBranch(n) {
  "use strict";
  if(!n) return null
  
  let value = n.value
  if(!n.left && !n.right) return value

  let left = n.left || null, right = n.right || null;
  
  return [value].concat(
    leftBranch(right),
    leftBranch(left))

}

let t = {
    "value": 1,
    "left": {
        "value": 2,
        "left": {
            "value": 3,
            "left": null,
            "right": null
        },
        "right": {
            "value": 4,
            "left": null,
            "right": null
        }
    },
    "right": {
        "value": 2,
        "left": {
            "value": 4,
            "left": null,
            "right": null
        },
        "right": {
            "value": 3,
            "left": null,
            "right": null
        }
    }
}
console.log(isTreeSymmetric(t)) //true

Answer 1

您实际上不需要检查节点或将其分组到数组中。就像你和@naomik 所做的那样，但返回 isTreeEqual(x.left, y.right) && isTreeEqual(x.right, y.left)。这会检查值和对称性(因为向右的右分支需要与向左的左分支对称，向右的左分支需要与向左的右分支对称)。

代码:

function isTreeSymmetric(t) {
    if (!t){
        return true
    }
    return isTreeEqual(t.left, t.right)
}

isTreeEqual = function(x, y) {
    if (!x && !y){
        return true
    }
    if (!x || !y){
        return false
    }
    if (x.value === y.value){
        return isTreeEqual(x.left, y.right) && isTreeEqual(x.right, y.left)
    } else {
        return false
    }
}