以下问题，主要是练习递归的使用，体会递归的思想。

Problem 654 最大数二叉树

Medium C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
/*********************************
Given an integer array with no duplicates. 
A maximum tree building on this array is defined as follow:

The root is the maximum number in the array.
The left subtree is the maximum tree constructed 
from left part subarray divided by the maximum number.

The right subtree is the maximum tree constructed 
from right part subarray divided by the maximum number.
Construct the maximum tree by the given array and output the root node of this tree.

Example 1:
Input: [3,2,1,6,0,5]
Output: return the tree root node representing the following tree:

	  6
	/   \
   3     5
	\    /
	 2  0
	   \
		1
Note:
The size of the given array will be in the range [1,1000].

***********************************/
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <sstream>
#include <queue>

using namespace std;

struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	
};

class Solution {
public:
	// method 1 使用迭代器 快了一点
	TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
		if (nums.empty()) {
			return nullptr;
		}
		auto it = max_element(nums.begin(), nums.end());
		TreeNode* root = new TreeNode(*it);
		vector<int> left(nums.begin(), it);
		vector<int> right(next(it), nums.end());
		root->left = constructMaximumBinaryTree(left);
		root->right = constructMaximumBinaryTree(right);
		return root;
	}

	// method 2  性能差
	TreeNode* construct(vector<int>& nums) {
		return build(nums, 0, nums.size());
	}

	TreeNode* build(vector<int> num, int start, int end) {
		if (start == end) {
			return nullptr;
		}
		int maxIndex = findMax(num, start, end);
		TreeNode* root = new TreeNode(num[maxIndex]);
		root->left = build(num, start, maxIndex);
		root->right = build(num, maxIndex + 1, end);
		return root;
	}

	int findMax(vector<int> num, int start, int end) {
		int index = start;
		int max = num[start];
		for (int i = start; i < end; i++) {
			if (num[i] > max) {
				index = i;
				max = num[i];
			}
		}
		return index;
	}
};

总结：
1. 使用迭代器速度快了一些
2. 递归循环查找速度显然慢了
3. 非递归版本速度更快，可利用栈实现

以下是 O(n)实现方式（摘自大佬）

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        vector<TreeNode*> stk;
        for (int i = 0; i < nums.size(); ++i)
        {
            TreeNode* cur = new TreeNode(nums[i]);
            while (!stk.empty() && stk.back()->val < nums[i])
            {
                cur->left = stk.back();
                stk.pop_back();
            }
            if (!stk.empty())
                stk.back()->right = cur;
            stk.push_back(cur);
        }
        return stk.front();
    }
};

递归统计二叉树结点在某区间内的和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**************************************************
Given the root node of a binary search tree, 
return the sum of values of all nodes with value 
between L and R (inclusive).

The binary search tree is guaranteed to have unique values.

Example 1:
Input: root = [10,5,15,3,7,null,18], L = 7, R = 15
Output: 32

Example 2:
Input: root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
Output: 23

Note:
The number of nodes in the tree is at most 10000.
The final answer is guaranteed to be less than 2^31.

*******************************************************/

#include <iostream>

using namespace std;

struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
	int sum = 0;

	int rangeSumBST(TreeNode* root, int L, int R) {
		tranverse(root, L, R); // 递归统计
		return sum;
	}

	void tranverse(TreeNode* root, int L, int R) {
		if (root == NULL)
			return;
		if (root->val <= R && root->val >= L) {
			sum += root->val;
		}
		tranverse(root->left, L, R);
		tranverse(root->right, L, R);
	}
};

简单二叉树剪枝

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/*
Question:
We are given the head node root of a binary tree,
where additionally every node's value is either a 0 or a 1.

Return the same tree where every subtree (of the 
given tree) not containing a 1 has been removed.

(Recall that the subtree of a node X is X, plus 
every node that is a descendant of X.)

Author: qiuyh
Date: 18/09/16
描述：一个二叉树，节点值为0或1，我们要对一棵
给定的二叉树剪枝，将其子树的节点值全为0的去除掉
思路：利用递归实现，将每一个节点视为根节点，
递归判断是否全为0，为0则该点置为null

*/

#include <iostream>
#include <string>

using namespace std;


struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};


class Solution {
	TreeNode* resultNode;
public:
	TreeNode * pruneTree(TreeNode* root) {
		// 找到空节点，就返回
		if (root == NULL) return root;
		// 继续下溯，若返回值可能为空或者不为空
		root->left = pruneTree(root->left);
		root->right = pruneTree(root->right);
		// 左右节点都为空而且值为0，则返回一个空指针
		if (root->left == NULL && root->right == NULL && root->val == 0) {
			return nullptr;
		}
		// 最后返回剪枝后的节点
		return root;

	}

};

矩阵递归搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/*
Question:An image is represented by a 2-D array of integers, 
each integer representing the pixel value of the image 
(from 0 to 65535).

Given a coordinate (sr, sc) representing the 
starting pixel (row and column) of the flood fill,
and a pixel value newColor, "flood fill" the image.

To perform a "flood fill", consider the starting 
pixel, plus any pixels connected 4-directionally to 
the starting pixel of the same color as the starting pixel, 
plus any pixels connected 4-directionally to those 
pixels (also with the same color as the starting pixel), 
and so on. Replace the color of all 
of the aforementioned pixels with the newColor.

At the end, return the modified image.

Author:qiuyh
Date: 18/09/16
描述：给定一个二维矩阵，和一个起点和一个颜色，
	该起点会向相邻水平竖直四个方向的点进行染色，
	  然后被染色的点成为新的点
思路：1.从起点开始，进行行列扫描，遇到相邻且颜色相同的点，
		继续加入起点，然后继续行列扫描， 时间复杂度大，不建议
	 2. 
*/
#include <iostream>
#include <vector>
using namespace std;


class Solution {
public:
	vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {

		if (image[sr][sc] == newColor) return image;
		int oldColor = image[sr][sc];
		image[sr][sc] = newColor;
		if (sc + 1 < image[sr].size() && oldColor == image[sr][sc + 1]) {
			floodFill(image, sr, sc + 1, newColor);

		}
		if (sc - 1 >= 0 && oldColor == image[sr][sc - 1]) {
			floodFill(image, sr, sc - 1, newColor);

		}
		if (sr + 1 < image.size() && oldColor == image[sr + 1][sc]) {
			floodFill(image, sr + 1, sc, newColor);

		}
		if (sr - 1 >= 0 && oldColor == image[sr - 1][sc]) {
			floodFill(image, sr - 1, sc, newColor);

		}
		return image;
	}
};

递归的思想和步骤：

  1. 递归就是找到重复相似的步骤，重复调用同一函数实现。
  2. 需要找到递归的终结条件。
  3. 明确多重递归之间的参数变量关系。