一、二叉树
一定要描述清楚递归的终止条件和递归过程
1、给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
/** * 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: int maxDepth(TreeNode* root) { if(root==NULL) return 0; int left = maxDepth(root->left); int right = maxDepth(root->right); return max(left,right)+1;//max()函数,是已经定义好的函数 } };
2、翻转二叉树
----------swap()函数,已经定义好的交换函数,可以直接使用-----------------/** * 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; } };
二、二叉树递归的终止条件
不要想当然的给出递归的终止条件,一定要经过分析和验证最后确定递归的终止条件。
1.给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树,以及目标和 sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树,以及目标和 sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2
/** * 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; if(hasPathSum(root->left,sum-root->val)) return true; if(hasPathSum(root->right,sum-root->val)) return true; return false; } };2、给出一个完全二叉树,求出该树的节点个数。
说明:
完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点。
示例:
输入:
1
/ \
2 3
/ \ /
4 5 6
输出: 6
解法一:
/** * 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: int countNodes(TreeNode* root) { if(root == NULL) return 0; return countNodes(root->left) + countNodes(root->right) + 1; } };解法二:如果右子树的高度等于整棵二叉树的高度-1的话,那么左子树一定是一棵满二叉树,这个时候我们就很容易的计算出总结点数nodes=2**(h)-1 + 1 +右子树节点数(这里的+1表示root节点)。如果右子树的高度不等于整棵二叉树的高度-1的话,那么左子树不一定是一棵满二叉树,但是有一点可以确定,右子树一定是一棵满二叉树,这个时候我们就很容易的计算出总结点数nodes=2**(h-1)-1 + 1 +左子树节点数(这里的+1表示root节点)
3、给定一个二叉树,检查它是否是镜像对称的。
例如,二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ \
2 2
\ \
3 3
/** * 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 isSymmetric(TreeNode* root) { if(root == NULL) return true; return leftAndRight(root->left,root->right); } bool leftAndRight(TreeNode* l,TreeNode* r){ if(l == NULL && r == NULL) return true; if (l == NULL|| r == NULL) return false; if(l->val != r->val) return false; return leftAndRight(l->left,r->right) & leftAndRight(l->right,r->left); } };4、给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回它的最小深度 2.
/** * 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: int minDepth(TreeNode* root) { if(root==NULL) return 0; TreeNode* node; queue<TreeNode*> que; int depth=1; que.push(root); while(!que.empty()){ int num=que.size(); while(num-->0){ node=que.front(); que.pop(); if(node->left==NULL&&node->right==NULL) return depth; if(node->left!=NULL) que.push(node->left); if(node->right!=NULL) que.push(node->right); } depth++; } return depth; } };
三、递归
1、写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项。斐波那契数列的定义如下:
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。
示例 1:
输入:n = 2
输出:1
示例 2:
输入:n = 5
输出:5
提示:
0 <= n <= 100
菲波那切数列不一定非要用递归来做,因为如果数比较多的时候,用递归会导致一些数重复计算
class Solution { public: int fib(int n) { if(n == 0 || n == 1) return n; int a = 1; int b = 0; for (int i = 1;i < n;i++){ a = a+b; b = a-b; a = a%1000000007; } return a; } };2、给定一个二叉树,它的每个结点都存放一个 0-9 的数字,每条从根到叶子节点的路径都代表一个数字。
例如,从根到叶子节点路径 1->2->3 代表数字 123。
计算从根到叶子节点生成的所有数字之和。
说明: 叶子节点是指没有子节点的节点。
示例 1:
输入: [1,2,3]
1
/ \
2 3
输出: 25
解释:
从根到叶子节点路径 1->2 代表数字 12.
从根到叶子节点路径 1->3 代表数字 13.
因此,数字总和 = 12 + 13 = 25.
/** * 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: int sumNumbers(TreeNode* root) { int num1 = 0; int num2 = 0; sum(root,num1,num2); return num2; } //num1指的是将每个节点的值乘以相应的10的倍数,num2是最终加和的结果 void sum(TreeNode* node,int num1,int& num2){ if(node == NULL) return; num1 = num1*10 + node->val; if(node->left==NULL && node->right==NULL){ num2 += num1; return; } sum(node->left,num1,num2); sum(node->right,num1,num2); } };