程序员面试金典---3

首个祖先

• 方法一：递归

  三种情况：

  • p、q分别在根节点的左右子树中，那么祖先就是root
  • p、q均位于根节点的左子树或右子树中，那么祖先在root.left或者root.right中递归。
  • p、q的其中一个节点是根节点，祖先为root

  var lowestCommonAncestor = function(root, p, q){
      // p、q的其中一个节点是根节点，祖先就是root
      if(!root || root === q || root === q){
          return root
      }
  	// p、q在左子树或者右子树上
      let left = lowestCommonAncestor(root.left, p ,q)
      let right = lowestCommonAncestor(root.right, p ,q)
      // p、q其中一个是根节点
      if(left && right) return root
      // 可能在左子树或者右子树
      return left ? left : right
  }
  

求和路径

• 回溯方法：

直接上代码：

var pathSum = function(root, sum) {
    // 如果为空
    if(!root) return 0;
    // 递归这个节点 + 递归右节点 + 递归左节点
    return dfs(root, sum) + pathSum(root.right, sum) + pathSum(root.left, sum)
    function dfs(root, sum){
        if(!root) return 0;
        // 如果相等于节点，直接递归右节点
        if(root.val === sum){
            return 1 + dfs(root.left, sum - root.val) + dfs(root.right, sum - root.val)
        }
        // 不相同，返回递归左节点和右节点
        return dfs(root.left, sum - root.val) + dfs(root.right, sum - root.val)
    }
};