513.找树左下角的值
层序遍历模板题。
//C#
public class Solution {
public int FindBottomLeftValue(TreeNode root) {
Queue<TreeNode> que = new Queue<TreeNode>();
int res = 0;
que.Enqueue(root);
while (que.Count != 0) {
int size = que.Count;
for (int i = 0; i < size; i++) {
TreeNode cur = que.Dequeue();
if (i == 0) {
res = cur.val;
}
if (cur.left != null) que.Enqueue(cur.left);
if (cur.right != null) que.Enqueue(cur.right);
}
}
return res;
}
}
递归方式,保证先做后右，并记录最大深度就是靠左的最大深度节点了，同时注意巧妙的控制返回条件，让return的时候是叶子结点，并保证没有空指针。
这里有一个误区，左边最大深度的节点，不一定是左子节点，对于递归来说，先遍历根节点的左的左，没有就是左的右，但都是左半部分，符合递归的顺序。
//C++ 代码随想录，回溯感觉还是怪
class Solution {
public:
int maxDepth = INT_MIN;
int result;
void traversal(TreeNode* root, int depth) {
if (root->left == NULL && root->right == NULL) {
if (depth > maxDepth) {
maxDepth = depth;
result = root->val;
}
return;
}
if (root->left) {
//depth++;
traversal(root->left, depth + 1); // 隐藏着回溯
//depth--;
}
if (root->right) {
//depth++;
traversal(root->right, depth + 1); // 隐藏着回溯
//depth--
}
return;
}
int findBottomLeftValue(TreeNode* root) {
traversal(root, 0);//这里应该是1，才符合深度从1开始计算。
return result;
}
};
其实还是这样更清晰，避免显式回溯。
class Solution {
public:
int result;
int maxDepth = INT_MIN;
int findBottomLeftValue(TreeNode* root) {
doit(root, 1);
return result;
}
void doit(TreeNode* cur, int depth) {
depth++;
if (cur->left == nullptr && cur->right == nullptr) {
if (depth > maxDepth) {
maxDepth = depth;
result = cur->val;
cout<<depth;
}
}
if (cur->left != nullptr) doit(cur->left, depth);
if (cur->right != nullptr) doit(cur->right, depth);
}
};
112. 路径总和
可以不用记录路径值求和的，Count-一直到叶子节点为0也符合条件，注意有返回值的递归在单层递归这一步一定要考虑返回值，比如这里我一开傲视就没有考虑左右遍历的时候return的逻辑，如果子递归都为true了，那直接返回true就行，一定要返回，要不然自递归的结果没法向上返回，终止条件的return只是边界条件（day17求路径那个不用返回是因为结果都保存在result数组里了，递归是void类型）。
class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
vector<int> path;
if (root == nullptr) return false;
return getPath(root, path, targetSum);
}
bool getPath(TreeNode* cur, vector<int> path, int targetSum) {
path.push_back(cur->val);
if (cur->left == nullptr && cur->right == nullptr) {
int sum = 0;
for (int i =0; i < path.size(); i++) {
sum += path[i];
}
if (sum == targetSum) return true;
return false;
}
if (cur->left != nullptr) {
if (getPath(cur->left, path, targetSum)) return true;
}
if (cur->right != nullptr) {
if (getPath(cur->right, path, targetSum)) return true;
}
return false;
}
};
回溯的时候注意恢复的是下一层的值，对于有返回值的递归，如果是bool类型返回值上层不再做操作，一路return就行，只有上层需要操作的时候再回溯。
//C#
public class Solution {
public int cnt;
public bool HasPathSum(TreeNode root, int targetSum) {
if (root == null) return false;
cnt = targetSum;
return HasPath(root);
}
public bool HasPath(TreeNode cur) {
Console.WriteLine(cnt);
cnt -= cur.val;
if (cur.left == null && cur.right == null) {
if (cnt == 0) return true;
return false;
}
if(cur.left != null) {
if(HasPath(cur.left))
return true;
cnt += cur.left.val;
}
if (cur.right != null) {
if (HasPath(cur.right))
return true;
cnt += cur.right.val;
}
return false;
}
}
113.路径总和ii
求路径的时候记录一下path，注意path和cnt都要回溯
//C++ 全局变量要回溯
class Solution {
public:
vector<int> path;
vector<vector<int>> result;
int cnt;
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
if (root == nullptr) return result;
cnt = targetSum;
doit(root);
return result;
}
void doit(TreeNode* cur) {
cout << cnt << endl;
cnt -= cur->val;
path.push_back(cur->val);
if (cur->left == nullptr && cur->right == nullptr) {
if (cnt == 0) {
result.push_back(path);
}
return;
}
if (cur->left != nullptr) {
doit(cur->left);
path.pop_back();
cnt += cur->left->val;
}
if (cur->right != nullptr) {
doit(cur->right);
path.pop_back();
cnt += cur->right->val;
}
}
};
利用参数复制避免回溯，如果递归的时候把结果数组作为参数传递，利用复制来避免回溯，比引用传参和全局变量要多开空间呀，毕竟每调用一次递归都要复制一次数组（C#里要new一次List），其实就是浅拷贝（只拷贝地址）和深拷贝（开辟新空间）。
public class Solution {
List<IList<int>> res = new List<IList<int>>();
public IList<IList<int>> PathSum(TreeNode root, int targetSum) {
if (root == null) return res;
doit(root, targetSum, new List<int>());
return res;
}
public void doit(TreeNode cur, int cnt, List<int> path1) {
List<int> path = new List<int>(path1);
cnt -= cur.val;
path.Add(cur.val);
if (cur.left == null && cur.right == null) {
if (cnt == 0) {
res.Add(path);
}
return;
}
if (cur.left != null) {
doit(cur.left, cnt, path);
}
if (cur.right != null) {
doit(cur.right, cnt, path);
}
}
}
106.从中序与后序遍历序列构造二叉树
- 大体思路就是先用后序数组内的最后一个中（根）元素切中序得到左右区间，再反过来根据中序切出来的区间切后序的左右区间，重复这个过程直到切到叶子结点，树也就构造完了。
- 切出来的区间定义要一致，要么都是左闭右闭，要么都是左闭右开。
- 中序是必须的，因为中序能够根据中间节点的位置把左右子树分开。
- 切割完的左右中序数组大小一定是和后序数组的大小相同的（这是必然）。
- 后序提供节点元素，前序提供左右子树。
- 构造的依据其实还是后序序列（递归停止的条件也是依据此），中序序列的作用是辅助对后序序列进行切割。
//C++
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (inorder.size() == 0 || postorder.size() == 0) return nullptr;
return doit(inorder, postorder);
}
TreeNode* doit(vector<int> & inorder, vector<int>& postorder) {
//1.分割产生了空节点，返回null
if (postorder.size() == 0) return nullptr;
//2.后序不为空，那么取后序数组最后一个元素作为节点元素
int rootValue = postorder[postorder.size() - 1];
TreeNode* root = new TreeNode(rootValue);
//叶子结点返回,不需要处理下面的左右区间（从下往上回溯构造）
if (postorder.size() == 1) return root;
//3.寻找中切割点
int index;
for (index = 0; index < inorder.size(); index++) {
if (inorder[index] == rootValue) break;
}
//4.切割中序数组得到左右中序区间
//左闭右开 [0, index)
vector<int> leftInorder(inorder.begin(), inorder.begin() + index);
//[index + 1, end)
vector<int> rightInorder(inorder.begin() + index + 1, inorder.end());
//5.根据左中序区间长度切割后序数组
postorder.resize(postorder.size() - 1);
vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());
// 以下为日志
cout << "----------" << endl;
cout << "leftInorder :";
for (int i : leftInorder) {
cout << i << " ";
}
cout << endl;
cout << "rightInorder :";
for (int i : rightInorder) {
cout << i << " ";
}
cout << endl;
cout << "leftPostorder :";
for (int i : leftPostorder) {
cout << i << " ";
}
cout << endl;
cout << "rightPostorder :";
for (int i : rightPostorder) {
cout << i << " ";
}
cout << endl;
//6.递归处理左右区间
root->left = doit(leftInorder, leftPostorder);
root->right = doit(rightInorder, rightPostorder);
return root;
}
};
不开辟数组精简版。
//C#
public class Solution {
public TreeNode BuildTree(int[] inorder, int[] postorder) {
if (inorder.Length == 0 || postorder.Length == 0) return null;
// 左闭右开的原则
return doit(inorder, 0, inorder.Length, postorder, 0, postorder.Length);
}
public TreeNode doit(int[] inorder, int inBegin, int inEnd, int[] post, int postBegin, int postEnd) {
if (postBegin == postEnd) return null;
int rootValue = post[postEnd - 1];
TreeNode root = new TreeNode(rootValue);
if (postEnd - postBegin == 1) return root;
int index;
for (index = inBegin; index < inEnd; index++) {
if (inorder[index] == rootValue) break;
}
int leftInBegin = inBegin;
int leftInEnd = index;
int rightInBegin = index + 1;
int rightInEnd = inEnd;
int leftPostBegin = postBegin;
int leftPostEnd = postBegin + index - inBegin;
int rightPostBegin = postBegin + index - inBegin;
int rihgtPostEnd = postEnd - 1;
root.left = doit(inorder,leftInBegin, leftInEnd, post, leftPostBegin, leftPostEnd);
root.right = doit(inorder, rightInBegin, rightInEnd,post, rightPostBegin, rihgtPostEnd);
return root;
}
}
105.从前序与中序遍历序列构造二叉树
前序和后序的不同就在于后序的最后一个元素作为节点，而前序是第一个元素作为节点，所以切分区间的时候左右中序的区间边界不用动[inBegin, index) [index + 1, inEnd)，左右后序区间[postBegin, postBegin + index - inBegin) [postBegin + index - inBegin, end - 1)变成左右前序空间[postBegin + 1, postBegin + 1 + index - inBegin) [postBegin + 1 + index - inBegin, end)即可，注意这时候用数组resize就没法把第一个元素去掉了。
public class Solution {
public TreeNode BuildTree(int[] preorder, int[] inorder) {
if (inorder.Length == 0 || preorder.Length == 0) return null;
// 左闭右开的原则
return doit(inorder, 0, inorder.Length, preorder, 0, preorder.Length);
}
public TreeNode doit(int[] inorder, int inBegin, int inEnd, int[] pre, int preBegin, int preEnd) {
if (preBegin == preEnd) return null;
int rootValue = pre[preBegin];
TreeNode root = new TreeNode(rootValue);
if (preEnd - preBegin == 1) return root;
int index;
for (index = inBegin; index < inEnd; index++) {
if (inorder[index] == rootValue) break;
}
int leftInBegin = inBegin;
int leftInEnd = index;
int rightInBegin = index + 1;
int rightInEnd = inEnd;
int leftpreBegin = preBegin + 1;
int leftpreEnd = preBegin + 1 + index - inBegin;
int rightpreBegin = preBegin + 1 + index - inBegin;
int rihgtpreEnd = preEnd;
root.left = doit(inorder,leftInBegin, leftInEnd, pre, leftpreBegin, leftpreEnd);
root.right = doit(inorder, rightInBegin, rightInEnd,pre, rightpreBegin, rihgtpreEnd);
return root;
}
}
C++ 使用数组，不用边界存，这种有多个参数的一定看清楚参数顺序，别但层递归的时候写反了，这两题都在这吃亏了。
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if (preorder.size() == 0|| inorder.size() == 0) return nullptr;
return doit(preorder, inorder);
}
TreeNode* doit(vector<int> preorder, vector<int> inorder) {
if (preorder.size() == 0) return nullptr;
TreeNode* cur = new TreeNode(preorder[0]);
cout<<cur->val<<endl;
if (preorder.size() == 1) return cur;
int index;
for (index = 0; index < inorder.size(); index++) {
if (inorder[index] == preorder[0]) break;
}
vector<int> leftIn(inorder.begin(), inorder.begin() + index);
vector<int> rightIn(inorder.begin() + index + 1, inorder.end());
vector<int> leftPre(preorder.begin() + 1, preorder.begin() + 1+ leftIn.size());
vector<int> rightPre(preorder.begin() + 1 + leftIn.size(), preorder.end());
cur->left = doit(leftPre, leftIn);
cur->right = doit(rightPre, rightIn);
return cur;
}
};
二刷看一下C#的数组拆分操作。
京公网安备 11010502036488号