内容简介：这篇博客我们主要来看二叉树和二叉树问题中使用递归来解决问题的思路。这类问题有时思路很简单，这是因为二叉树具有天然的递归结构，所以我们使用递归的解法解决二叉树有关的问题就变得非常明显。有的时候递归的终止条件是存在陷阱的。采取递归来解决这个问题，我们可以从头结点开始，向它的左右孩子节点寻找sum-根节点的值，不断向下寻找。这道题陷阱在于终止条件不是node == NULL。
这篇博客我们主要来看二叉树和二叉树问题中使用递归来解决问题的思路。这类问题有时思路很简单，这是因为二叉树具有天然的递归结构，所以我们使用递归的解法解决二叉树有关的问题就变得非常明显。
二叉树天然的递归结构
- 语义
- 终止条件
- 递归过程
例子
二叉树前序遍历
//前序遍历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;
}
};
复制代码
以上所述就是小编给大家介绍的《leetcode题解(二叉树和递归问题)》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
UNIX环境高级编程
W.Richard Stevens Stephen A.Rago、Stephen A. Rago / 人民邮电出版社 / 2006-2 / 99.00元
本书是被誉为UNIX编程“圣经”的Advanced Programming in the UNIX Environment一书的更新版。在本书第一版出版后的十几年中，UNIX行业已经有了巨大的变化，特别是影响UNIX编程接口的有关标准变化很大。本书在保持了前一版的风格的基础上，根据最新的标准对内容进行了修订和增补，反映了最新的技术发展。书中除了介绍UNIX文件和目录、标准I/O库、系统数据文件和信......一起来看看 《UNIX环境高级编程》 这本书的介绍吧!
