前言
今日文案：
平静的湖面只有呆板的倒映，奔腾的激流才有美丽的浪花。幸福不是靠别人来布施，而是要自己去赢取。生命的意义在不断挑战自己，战胜自己！
一、平衡二叉树
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
解题思路：
左右子树的高度差不超过1，和我们之前写过的遍历所有的节点一样，只要左树节点-右数节点的绝对值<1就行。那么我们的递归，每次都是在一个中节点处比较两边就行。
class Solution { public: int treehight(TreeNode*root) { int res=0; if(root==0) { return 0; } int leftnode=treehight(root->left); if(leftnode==-1) return -1; int rightnode=treehight(root->right); if(rightnode==-1) return -1; if(abs(leftnode-rightnode)>1) res=-1; else res=max(leftnode,rightnode)+1; return res; } bool isBalanced(TreeNode* root) { int w=treehight(root); if(w==-1) return false; else return true; } };
二、二叉树所有路径
思路：
在我们遍历了一遍路劲之和一定要记得回溯，把里面的符号删去
class Solution { public: void traversal(TreeNode*cur,string path,vector<string> &ans) { path+=to_string(cur->val); //临时变量，会自动回溯 if(cur->left==0&cur->right==0) { ans.push_back(path); } if(cur->left) //一直往左 { path+="->"; traversal(cur->left,path,ans); path.pop_back(); //回溯"->" path.pop_back(); } if(cur->right) //回中后往右 { path+="->"; traversal(cur->right,path,ans); path.pop_back(); //回溯"->" path.pop_back(); } } vector<string> binaryTreePaths(TreeNode* root) { vector<string> ans; string path; if(root==0) return ans; traversal(root,path,ans); return ans; } };
三、左叶子之和
解题思路：
左叶子，关键是找到左边的，还有叶子。
class Solution { public: int sumOfLeftLeaves(TreeNode* root) { if(root==NULL) { return 0; } if(root->left==0&&root->right==0) { return 0; } //返回条件 int leftnums=sumOfLeftLeaves(root->left); //找到叶子就返回0 if(root->left&&root->left->left==0&&root->left->right==0) //判断是不是左叶子 leftnums=root->left->val; //是就记录进和 int rightnums=sumOfLeftLeaves(root->right); //往右走找左叶子 int ans=rightnums+leftnums; return ans; } };
总结
继续加油。
