二叉树递归详解编程语言

递归终止条件

我们来看一下二分搜索树的释放，这就是一个典型的递归问题

   function destroy(node){ 
      if(node == null) return; 
      //如果当前节点不为空，则释放节点的左节点和右节点 
      destroy(node.left); 
      destroy(node.right); 
      delete node; 
      count--; 
   }

这个递归包括两个部分，一个是递归终止条件，一个是递归的执行。我们知道递归是不断地将当前函数压入函数栈，如果没有if(node == null) return 这个终止条件，当函数栈被压满之后就会发生栈溢出(栈的length是有限的)。

二叉树的最大深度

当我们要求二叉树的最大深度，用递归很容易能解决这一问题。

   function maxDepth(root){ 
      if(root == null) return 0; 
      var leftMaxDepth = maxDepth(root.left); 
      var rightMaxDepth = maxDepth(root.right); 
      //每一个节点对比两边的深度的大小 
      return Math.max(leftMaxDepth, rightMaxDepth) + 1; 
   }

当节点为空的时候return，假设我们有只有根节点和右子节点，那么左子节点为空，我们得到的就是右子节点的depth + 1。
那么如果我们要求二叉树的最小深度呢，二叉树的最小深度为根节点到最近叶子节点的距离。(如果根节点的左子树为空，那么最小深度要到右子树中找)

   function minDepth(root){ 
      if(root == null)  return 0; 
      return getMin(root); 
   } 
   function getMin(root){ 
      //排除了根节点的情况，如果根节点为null，在上面已经返回0 
      if(root == null) return Number.MAX_SAFE_INTEGER; 
      if(root.left == null && root.right == null) return 1; 
      var leftMinDepth = getMin(root.left); 
      var rightMinDepth = getMin(root.right); 
      return Math.min(leftMinDepth, rightMinDepth) + 1; 
   }

反转二叉树

利用递归来反转二叉树非常容易

   function invertTree(root){ 
       if(root == null) return null; 
       //递归调用要写在swap操作前，因为祖先节点要在子节点反转之后才进行交换 
       invertTree(root.left); 
       invertTree(root.right); 
       swap(root.left, root.right); 
       return root; 
   }

Path Sum

来看这样一个问题，给出一个二叉树(每个节点的val上存放一个数字)以及一个数字sum，判断在这棵二叉树上是否存在一条从根到叶子的路径，其路径上的所有节点和为sum

   function hasPathSum(root, sum){ 
        if(root == null) return sum == 0; 
        if(hasPathSum(root.left, sum - root.val)) return true; 
        if(hasPathSum(root.right, sum - root.val)) return true; 
        return false; 
   }

注意，这里当sum等于根节点的val的时候，假如左子树为空，那么此时sum为０，返回了true，但是并不符合题目要求，因为要求是判断是否存在一条从根节点到叶子节点的路径。

   function hasPathSum(root, sum){ 
        if(root == null) return false; 
        if(root.left == null && root.right == null) return sum == 0; 
        if(hasPathSum(root.left, sum - root.val)) return true; 
        if(hasPathSum(root.right, sum - root.val)) return true; 
        return false; 
   }

Binary Tree paths

来看这样一个问题，给出一个二叉树，返回所有表示从根节点到叶子节点路径的字符串，结果示例为[‘1->2->5’, ‘1->3’]
我们来分析一下，这个问题实际上是根节点->{左子树的路径字符串} + 根节点->{右子树的字符串}

   function binaryTreePaths(root){ 
       var res = []; 
       if(root == null) return res; 
       if(root.left == null && root.right == null){ 
          res.push(root.val); 
          return res; 
       } 
       var leftS = binaryTreePaths(root.left); 
       for(var i = 0; i < leftS.length; i++){ 
           res.push(root.val + '->' + leftS[i]); 
       } 
       var rightS = binaryTreePaths(root.right); 
       for(var i = 0; i < rightS.length; i++){ 
           res.push(root.val + '->' + rightS[i]); 
       } 
       return res; 
   }