二叉树的递归算法

递归在二叉树算法中的思路分析

在提出具体问题之前，首先理解一下：二叉树其实是递归的。在递归算法里面，常见的两种思路是：（1）Top-down；（2）Bottom-up。 （1）Top-down解法：首先是访问根节点，利用本次传进来的参数更新答案，再依据根节点和叶子节点之间的逻辑关系，推断出left_params和right_params和params之间的关系，以函数参数的形式传递给左子树节点和右子树节点,并且递归调用该函数。下面是解决问题的一般步骤：

return specific value for null node
update the answer if needed                      // anwer <-- params
left_ans = top_down(root.left, left_params)      // left_params <-- root.val, params
right_ans = top_down(root.right, right_params)   // right_params <-- root.val, params 
return the answer if needed                      // answer <-- left_ans, right_ans

（2）Bottom-up解法：对于某一节点，如果我们能够解决掉其左右子树的问题，那么，就能根据答案解决该节点的问题。

return specific value for null node
left_ans = bottom_up(root.left)          // call function recursively for left child
right_ans = bottom_up(root.right)        // call function recursively for right child
return answers                           // answer <-- left_ans, right_ans, root.val
return max(left_depth, right_depth) + 1  // return depth of the subtree rooted at root

下面以求二叉树的最大深度为例： 使用Top-down解法，

class Solution{
  public:
  int maxDepth(TreeNode* root){
    ans = 0;
    traverse(root,1);
  };
  void traverse(TreeNode* root,int depth){
    if(root->left==nullptr&&root->right==nullptr){
      return max(ans,depth);//update answer 
    }
    traverse(root->left,depth+1);//use depth and relationship between root and root->left call function
    traverse(root->right,depth+1);
  };
  private:
  int ans;
};


使用Bottom-up方法：

class Solution{
      public:
      int maxDepth(TreeNode* root){
        if(root==nullptr) return 0;
        int left_depth = maxDepth(root->left);
        int right_depth = maxDepth(root->right);
        return max(left_depth,right_depth) + 1;
      };
    };