javascript - 任意树的高度

Question

给定一棵任意树，其中每个节点都有一个指向其第一个子节点 ( node.left) 及其最近的兄弟节点 ( ) 的指针node.right，如何找到树的高度？

这就是我所拥有的：

function height(tree) {
  let h = 0;
  const queue = [[tree.root, 1]]; // pair (Node, depth)
  let n = 0; // use a pointer rather than shifting the array
  while (n < queue.length) {
    const [node, d] = queue[n];
    if (d > h) h = d; // if the current depth is greater then the max height so far, then update the max height
    // Traverse the siblings
    let r = node.right;
    while (r) {
      queue.push([r, d]); // siblings have the same depth
      r = r.right;
    }
    node.left && queue.push([node.left, d + 1]); // traverse the children
    n++; // go to the next Node
  }
  return h;
}

它不是递归的，因为树可能真的很大而且我得到溢出错误。这段代码应该可以工作，但只是想知道是否有不同/更好的方法来做到这一点。

标签： javascriptperformancetree

Answer 1

function height(node){
   if(!node) return 0;
   var leftHeight = height(node.left);
   var rightHeight = height(node.right);

   return Math.max(leftHeight, rightHeight) + 1;
}

最好的方法是使用递归。它干净易读。