婚纱网站怎么做,什么是网站开发公司电话,中国移动网站官网,专业的家居行业网站开发LeetCode 110 平衡二叉树
递归写法很简单#xff0c;直接自底向上每个节点判断是否为空#xff0c;为空说明该层高度为0。不为空用一个int型变量l记录左子树高度#xff08;递归调用该函数自身#xff09;#xff0c;一个int型变量r记录右子树高度#xff08;同样递归调…LeetCode 110 平衡二叉树
递归写法很简单直接自底向上每个节点判断是否为空为空说明该层高度为0。不为空用一个int型变量l记录左子树高度递归调用该函数自身一个int型变量r记录右子树高度同样递归调用该函数自身将l和r相减取绝对值大于1说明不平衡直接返回-1此外还需要判断l和r是否已经是-1这种情况下也直接返回-1。这样判断的底层原理是计算每个节点返回值是高度还是-1取-1也是因为不会影响到正常高度的计算。最后来到递归遍历阶段返回1max(l,r)即可。
这个过程中最上层是确认返回条件中间是确认参数和返回值最下层是递归逻辑。
代码如下
class Solution {
public:int height(TreeNode* root) {if (!root) return 0; int l height(root-left), r height(root-right);if (abs(l - r) 1) return -1;else if (l -1) return -1;else if (r -1) return -1;return 1 max(l, r); }bool isBalanced(TreeNode* root) {if (height(root) ! -1) return true;else return false;}
};
LeetCode 257 二叉树的所有路径
这题对于学过回溯法的人来说很明显是回溯了。新手可能会有点头痛。
回溯法本质上也是一种递归是一种暴力枚举。在递归过程中如果没有后续状态就会把当前这一条路径放进存储结果的集合中返回当前函数到上一层。而如果有后续状态就先记录当前路径将当前路径加上其中一个下一状态用这一路径继续递归直到返回在其语句后面还要将路径还原至递归前。相当于先给你一个苹果让你吃完之后看苹果是啥样子记录下来再一路回到你吃苹果之前把苹果给别人吃看又是啥样子。这样的递归过程就能实现一种暴力枚举。
代码如下
class Solution {
private:vectorstring res;string path ;
public:void backtracking(TreeNode* cur) {if (!cur-left !cur-right) {res.push_back(path);}else {if (cur) {string temp path;if (cur-left) {string s to_string(cur-left-val);path -;path s;backtracking(cur-left);path temp;}if (cur-right) {string s to_string(cur-right-val);path -;path s;backtracking(cur-right);path temp;}}}}vectorstring binaryTreePaths(TreeNode* root) {if (!root) return res;string s to_string(root-val);path s;backtracking(root);return res;}};
还需要注意的有递归起始状态返回条件和每次递归逻辑的确定。
本题还可以尝试迭代法来写。暂时先放这等会来写。 LeetCode 404 左叶子之和
其实前序遍历等遍历方式中选一种就行了需要注意的是左叶子首先要是某个叶子的左节点然后还要是叶子节点。可以顺便满足这个遍历情况的前序遍历是肯定可以的。中序遍历也可以层序遍历和后续遍历会比较麻烦一点。这里给出前序遍历实现的代码如下
class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {int sum 0;TreeNode* cur root;queueTreeNode* myque;while (cur || !myque.empty()) {while (cur) {myque.push(cur);if (cur-left) {if (!cur-left-left !cur-left-right)sum cur-left-val;}cur cur-left;}cur myque.front();myque.pop();cur cur-right;}return sum;}
};