Day20 222完全二叉树的节点个数 110平衡二叉树 257二叉树的所有路径
222 完全二叉树的结点个数
? ? ? ? 本题先不把它当成完全二叉树来看,用广度优先和深度优先搜索分别遍历,也能达到目的,只要将之前的代码稍加修改即可。注意后序遍历时的result要加上自身本身的那个结点。
//后序递归遍历
class Solution {
public:
int countNodes(TreeNode* root) {
if(root==nullptr) return 0;
int leftnum = countNodes(root->left);
int rightnum = countNodes(root->right);
int result = leftnum + rightnum +1;
return result;
}
};
//层序遍历
class Solution {
public:
int countNodes(TreeNode* root) {
queue<TreeNode*> que;
int result = 0;
if(root != NULL)
que.push(root);
while(!que.empty())
{
int size = que.size();
while(size--)
{
TreeNode* node = que.front();
que.pop();
result++;
if(node->left)
que.push(node->left);
if(node->right)
que.push(node->right);
}
}
return result;
}
};
? ? ? ? 既然本题给出了条件完全二叉树,那就可以用完全二叉树的方法来做。可以继续使用递归法,终止条件要稍微变一下,要根据左右深度是否相同来判断子树是不是满二叉树,如果是的话就返回2的n次方-1,不是的话就继续递归。为什么左右深度相等就一定是满二叉树呢,这取决于完全二叉树的特性,也就是最后那层肯定是连续的,不存在中间为空的情况。
class Solution {
public:
int countNodes(TreeNode* root) {
if (root == nullptr) return 0;
TreeNode* left = root->left;
TreeNode* right = root->right;
int leftDepth = 0, rightDepth = 0; // 这里初始为0是有目的的,为了下面求指数方便
while (left) { // 求左子树深度
left = left->left;
leftDepth++;
}
while (right) { // 求右子树深度
right = right->right;
rightDepth++;
}
if (leftDepth == rightDepth) {
return (2 << leftDepth) - 1; // 注意(2<<1) 相当于2^2,所以leftDepth初始为0
}
return countNodes(root->left) + countNodes(root->right) + 1;
}
};
?110 平衡二叉树
递归:
????????要求高度,首先想到要后序遍历,终止条件为遍历到空节点,单层递归逻辑为:分别求出本节点左右子树的高度,如果高度等于-1,就说明左右子树之一不平衡,如果均不为-1, 就继续往下进行,比较左右子树的高度差,大于1说明有问题,返回-1,其余情况正常算高度。
class Solution {
public:
int getHeight(TreeNode* node){
if(node == nullptr) return 0; //终止条件
int leftHeight = getHeight(node->left);
if(leftHeight==-1) return -1;
int rightHeight = getHeight(node->right);
if(rightHeight == -1) return -1;
return (abs(leftHeight-rightHeight) > 1 ? -1 : (1+max(leftHeight,rightHeight)));}
bool isBalanced(TreeNode* root) {
return (getHeight(root)==-1 ? false : true);
}
};
迭代:
????????本题也可以通过迭代法来进行遍历,但是不能直接用层序遍历来求高度,这就体现出求高度和求深度的不同之处。本题的迭代方式可以先定义一个函数专门求高度。
class Solution {
public:
int getDepth(TreeNode*node)
{
queue<TreeNode*> que;
if(node!=nullptr) que.push(node);
int depth = 0;
while(!que.empty())
{
int size = que.size();
depth++;
while(size--)
{
TreeNode* cur = que.front();
que.pop();
if(cur->left) que.push(cur->left);
if(cur->right) que.push(cur->right);
}
}
return depth;
}
bool isBalanced(TreeNode* root) {
queue<TreeNode*> que;
if(root == nullptr) return true;
else que.push(root);
while(!que.empty())
{
int size = que.size();
while(size--)
{
TreeNode*node=que.front();
que.pop();
if(abs(getDepth(node->left)-getDepth(node->right))>1)
return false;
if(node->left) que.push(node->left);
if(node->right) que.push(node->right);
}
}
return true;
}
};
257 二叉树的所有路径??
? ? ? ? ?本题很明显要进行前序遍历,才方便让父亲节点指向孩子节点,找到对应的路径。但是既然要输出所有的路径,我觉得本题是时候该考虑回溯了。
? ? ? ? ?首先是递归法:1.参数返回值:传入根节点,记录每一条路径的path,存放结果的result。
2.递归终止条件。在写递归时都习惯了写cur==null终止,但是本题如果这么写会比较麻烦,因为本题是要找到叶子节点,就结束把路径放进result里的处理了。那么为什么要用vector<int> path来记录路径呢,因为单层递归的逻辑时,要做回溯,使用vector方便回溯过程。3.确定单层递归逻辑,因为前序遍历,所以先处理中间结点,之后就是递归和回溯的过程。
????????要注意:回溯要和递归永远在一起,世界上最遥远的距离是你在花括号里,而我在花括号外!有一个递归,就要对应一个回溯!
? ? ? ? 整体代码如下:
class Solution {
private:
void traversal(TreeNode* cur, vector<int>& path, vector<string>& result) {
path.push_back(cur->val); // 中,中为什么写在这里,因为最后一个节点也要加入到path中
// 这才到了叶子节点
if (cur->left == NULL && cur->right == NULL) {
string sPath;
for (int i = 0; i < path.size() - 1; i++) {
sPath += to_string(path[i]);
sPath += "->";
}
sPath += to_string(path[path.size() - 1]);
result.push_back(sPath);
return;
}
if (cur->left) { // 左
traversal(cur->left, path, result);
path.pop_back(); // 回溯
}
if (cur->right) { // 右
traversal(cur->right, path, result);
path.pop_back(); // 回溯
}
}
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> result;
vector<int> path;
if (root == NULL) return result;
traversal(root, path, result);
return result;
}
};
? ? ? ? ?每次回溯都要pop出此时容器里存放的那个数字,这样就能找出不同的路径了。为什么要用引用呢因为既然每次都pop了,所以说这个path每次都是在变的。
可以精简成如下代码:
class Solution {
private:
void traversal(TreeNode* cur, string path, vector<string>& result) {
path += to_string(cur->val); // 中
if (cur->left == NULL && cur->right == NULL) {
result.push_back(path);
return;
}
if (cur->left) traversal(cur->left, path + "->", result); // 左
if (cur->right) traversal(cur->right, path + "->", result); // 右
}
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> result;
string path;
if (root == NULL) return result;
traversal(root, path, result);
return result;
}
};
? ? ? ? ?这个代码里也有递归回溯,因为传入的这个string并不是引用形式,每次执行完毕以后,返回到上一个都不会让这次的影响对上一次进行改变,所以-》要写在递归函数里面,如果写成:
path += "->";
traversal(cur->left, path, result); // 左
? ? ? ? ?path就会被改变以后再进行递归,无法进行回溯,这回导致-》重复。如果非要这么写,就得用第一种方法把他pop出去:
if (cur->left) {
path += "->";
traversal(cur->left, path, result); // 左
path.pop_back(); // 回溯 '>'
path.pop_back(); // 回溯 '-'
}
if (cur->right) {
path += "->";
traversal(cur->right, path, result); // 右
path.pop_back(); // 回溯 '>'
path.pop_back(); // 回溯 '-'
}
? ? ? ? ?本题也可以采用非递归的方式,类似于前序遍历的迭代法,不过要定义两个栈,一个是正常迭代法里的那个遍历栈,另一个是保存每次路径的栈:
class Solution {
public:
vector<string> binaryTreePaths(TreeNode* root) {
stack<TreeNode*> treeSt;// 保存树的遍历节点
stack<string> pathSt; // 保存遍历路径的节点
vector<string> result; // 保存最终路径集合
if (root == NULL) return result;
treeSt.push(root);
pathSt.push(to_string(root->val));
while (!treeSt.empty()) {
TreeNode* node = treeSt.top(); treeSt.pop(); // 取出节点 中
string path = pathSt.top();pathSt.pop(); // 取出该节点对应的路径
if (node->left == NULL && node->right == NULL) { // 遇到叶子节点
result.push_back(path);
}
if (node->right) { // 右
treeSt.push(node->right);
pathSt.push(path + "->" + to_string(node->right->val));
}
if (node->left) { // 左
treeSt.push(node->left);
pathSt.push(path + "->" + to_string(node->left->val));
}
}
return result;
}
};
? ? ? ? ?这两个栈是紧密联系的,上面动的时候,下面也会跟着动。这里的treeSt肯定是只遍历一遍的,但是pathSt里面存的是一个路径,上次遍历的部分会依旧保留,记录了之前遍历过的部分。
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!