二叉树最近公共父节点

给定一颗二叉树，以及其中的两个node（地址均非空），要求给出这两个node的最近的公共父节点。请实现函数FindSParent

实现

采用深度遍历

function FindSParent(root,p,q){
  let result
  function hasNode(node,p,q){
    if(node===null) return false;
    // 递归获取左右两边匹配节点情况
    let left = hasNode(node.left,p,q)
    let right = hasNode(node.right,p,q)
    // 情况1：左右两边都匹配到节点，说明此节点为公共父节点
    // 情况2：左右两边有一边匹配到节点，且当前节点也匹配到节点，说明当前节点为公共父节点
    if((left&&right)||(left||right)&&(node.val===p.val||node.val===q.val)){
      result = node
    }
    // 返回节点匹配情况
    return left || right || node.val === p.val || node.val === q.val
  }

  hasNode(root,p,q)
  return result
}