赞
踩
day15 二叉树第三天
代码随想录题目链接:代码随想录
给定一个二叉树,判断它是否是 平衡二叉树
回顾定义:平衡二叉树指的是左右子树高度相差不大于1的树
用递归的方法做,那就是比较两个子树的最大深度,如果相差大于1,则返回-1告诉上层,这是不平衡树的节点,否则返回最大深度
代码如下:
class Solution { public: int getDepth(TreeNode * curr) { if(!curr) return 0; int leftDepth = getDepth(curr->left); int rightDepth = getDepth(curr->right); if(leftDepth == -1 || rightDepth == - 1) return -1; if(abs(leftDepth - rightDepth) > 1) return - 1; return max(leftDepth, rightDepth) + 1; } bool isBalanced(TreeNode* root) { if(!root) return true; int Depth = getDepth(root); if(Depth == -1) return false; else return true; } };
代码随想录题目链接:代码随想录
给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
这里就要用回溯了
回溯算法的想法类似于试错,一条路走到底发现错了,那就撤回几步,换另一条路走
所以本题也一样,先一条路走到底,得到一个路径后,返回上一个节点,走另一个子树,如果没有子树了,就再回去一格,重复下去
所以递归法的话,应该是传入当前树的根节点,而且有一个数组可以存这条路遍历过来的节点值
如果这个节点是叶节点,那就可以从数组中取数字出来做答案,存在result中,接着回溯
代码如下:
class Solution { public: void traversal(TreeNode* curr, vector<int>& path, vector<string>& result) { if(!curr->left && !curr->right) { string temp; for(auto ele : path) { temp += to_string(ele); temp += "->"; } temp += to_string(curr->val); result.push_back(temp); } if(curr->left) { path.push_back(curr->val); traversal(curr->left, path, result); path.pop_back(); } if(curr->right) { path.push_back(curr->val); traversal(curr->right, path, result); path.pop_back(); } } vector<string> binaryTreePaths(TreeNode* root) { vector<string> result; vector<int> path; if(!root) return {}; traversal(root, path, result); return result; } };
回溯算法体现在path的push和pop,push+递归可以理解为向下试错,试错结束后pop就能体现出回溯的效果
代码随想录题目链接:代码随想录
给定二叉树的根节点 root ,返回所有左叶子之和。
第一反应用层序遍历秒了,但是层序遍历没法判断当前节点是不是左叶子节点,只能判断它是这层最左边的点
实际上需要通过父节点来判断当前节点是不是左叶子节点
所以传入父节点,检查其左节点不为空且左节点的左右节点为空,那么这个父节点就有一个左叶子节点,加进去就行
代码如下:
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if(!root) return 0;
int sum = 0;
sum += sumOfLeftLeaves(root->left);
if(root->left && !root->left->left && !root->left->right)
{
sum += root->left->val;
}
sum += sumOfLeftLeaves(root->right);
return sum;
}
};
代码随想录题目链接:代码随想录
给你一棵 完全二叉树 的根节点 root ,求出该树的节点个数。
完全二叉树 的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点。
这个真的是层序遍历秒了
代码如下:
class Solution { public: int countNodes(TreeNode* root) { if(!root) return 0; queue<TreeNode *> que; que.push(root); int result = 0; while(!que.empty()) { int length = que.size(); for(int i = 0; i < length ; i ++) { result ++; TreeNode * curr = que.front(); que.pop(); if(curr->left) que.push(curr->left); if(curr->right) que.push(curr->right); /*Add function here*/ } } return result; } };
模板参考链接:层序遍历
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。