leetcode题解(二叉树和递归问题)

这篇博客我们主要来看二叉树和二叉树问题中使用递归来解决问题的思路。这类问题有时思路很简单，这是因为二叉树具有天然的递归结构，所以我们使用递归的解法解决二叉树有关的问题就变得非常明显。

二叉树天然的递归结构

• 语义
• 终止条件
• 递归过程

例子

二叉树前序遍历

//前序遍历node节点
void preorder(TreeNode * node){
	if (node == NULL){ 
    	return; //终止条件
    }
    
    cout << node -> val;
    preorder(node -> left);
    preorder(node -> right);//递归过程
}

复制代码

二叉树查找某个节点

bool contain(Node *node, key key){
	if (node == NULL)
    	return false;
        
    if (key == node->key)
    	return true;
        
    if( contain(node -> left,key) || contain(node -> right, key))
    	return true;
        
    return false;
}

复制代码

删除一颗二叉树

void destroy(Node * node){
	if(node == NULL)
    	return;
    destroy(node->left);
    destroy(node->right);
    
    delete node;
    count --;
}

复制代码

leetcode 104. 二叉树的最大深度

class Solution {
public:
    //求节点root的深度
    int maxDepth(TreeNode* root) {
        //终止条件
        if(root == NULL){ 
            return 0;
        }
        
        return 1 + max(maxDepth(root -> left), maxDepth(root -> right));
        
    }
};
复制代码

相似问题

leetcode 111

一个简单的二叉树问题引发的血案

leetcode 226. 翻转二叉树

代码实现

/// Definition for a binary tree node.
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    
    class Solution {
    public:
        TreeNode* invertTree(TreeNode* root) {
    
            if ( root == NULL ) {
                return NULL;
            }
    
            invertTree( root->left );
            invertTree( root->right );
            swap ( root->left, root->right );
    
            return root;
        }
    };
    
复制代码

相似问题

leetcode 100

leetcode 101

leetcode 222

leetcode 110

注意递归的终止条件

有的时候递归的终止条件是存在陷阱的。

leetcode 112. 路径总和

解题思路

采取递归来解决这个问题，我们可以从头结点开始，向它的左右孩子节点寻找sum-根节点的值，不断向下寻找。这道题陷阱在于终止条件不是node == NULL。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if (root == NULL){
            return false;
        }
        
        //为叶子节点
        if (root -> left == NULL && root -> right == NULL){
            return root -> val == sum;
        }
        
        return hasPathSum(root -> left, sum - root -> val) || hasPathSum(root -> right, sum - root -> val);
        
        
        return false;
        
    }
}; 
复制代码

定义递归问题

我们如何使用递归的返回值来解决问题。 函数的语义很重要

leetcode 257. 二叉树的所有路径

思路

对于每一个节点，就是该节点的值加上“->”再加上左子树的路径字符串和右子树路径字符串。当到达叶节点时，将字符串加入结果集。

实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        
        if (root == NULL){
            return res;
        }
        
        if (root -> left == NULL && root -> right == NULL){
            res.push_back(to_string(root -> val));
            return res;
        }
        
        vector<string> lefts = binaryTreePaths(root -> left);
        
        for(int i = 0; i < lefts.size(); i++){
            res.push_back(to_string(root -> val) + "->" + lefts[i]);
        }
        
        
        vector<string> rights = binaryTreePaths(root -> right);
        
        for(int i = 0; i < rights.size(); i++){
            res.push_back(to_string(root -> val) + "->" + rights[i]);
        }
        
        return res;
        
    }
};

复制代码

相似问题

leetcode 113

leetcode 129

稍复杂的递归逻辑

leetcode 437. 路径总和 III

解题思路

猛地一看这个描述，和我们之前的Path Sum是一样的。但是区别在于我们对于路径的定义不一定要起始于根节点，终止于叶子结点，路径可以从任意节点开始，但是只能是向下走的。

在一个节点上要通过三个部分获得答案，第一个部分看看有没有一条路径，它包含node这个节点，并且它的和为sum,这个路径我们进入findPath这个子过程，这个子过程本身又是一个递归函数。另外的两部分就是要在node的左右子树去寻找没有这个ndoe节点的值，有没有这样的路径，他们的和仍然为sum，这件事就是我们PathSum这个函数所做的。在node->left和node->right分别调用PathSum的过程中，他们也会调用findPath来求解。

代码实现

#include <iostream>
    
    using namespace std;
    
    // Definition for a binary tree node.
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    
    class Solution {
    
    public:
        // 在以root为根节点的二叉树中,寻找和为sum的路径,返回这样的路径个数
        int pathSum(TreeNode* root, int sum) {
    
            if ( root == NULL) {
                return 0;
            }
    
            int res = findPath( root, sum );
            res += pathSum( root->left,  sum );
            res += pathSum( root->right, sum );
    
            return res;
        }
    
    private:
    
        // 在以node为根节点的二叉树中,寻找包含node的路径,和为sum
        // 返回这样的路径个数
        int findPath( TreeNode* node, int num){
    
            if ( node == NULL ) {
                return 0;
            }
    
            int res = 0;
            if ( node->val == num ) {
                res += 1;
            }
    
            res += findPath( node->left, num - node->val );
            res += findPath( node->right, num - node->val );
    
            return res;
        }
    };
    
复制代码

二分搜索树中的问题

leetcode 235. 二叉搜索树的最近公共祖先

思路

二分搜索树：

每个节点的键值大于左孩子

每个节点的键值小于右孩子

以左右孩子为跟的子树仍为二分搜索树

如果我们给的p,q节点都小于node节点，那么他们最近的公共祖先一定在node左边。如果我们给的p,q节点都大于node节点，那么他们最近的公共祖先一定在ndoe右边。如果一小一大，那么node一定是最近的公众祖先。

代码实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        assert(p != NULL && q != NULL);
        
        if (root == NULL){
            return NULL;
        }
        
        if ((root -> val > p -> val) && (root -> val > q -> val))
            return lowestCommonAncestor(root -> left, p, q);
        
        if ((root -> val < p -> val) && (root -> val < q -> val))
            return lowestCommonAncestor(root -> right, p, q);
        
        //p 与q在root的两侧， 则root必为公共祖先，包含p为q的祖先
        return root;
    }
};

复制代码