LeetCode 110. 平衡二叉树
题目：
给定一个二叉树，判断它是否是高度平衡的二叉树。
思路:
采用后序遍历，从最下层的节点开始遍历，如果碰到某一个子二叉树不是平衡二叉树，那么与这个子二叉树相关的就都不是平衡二叉树。
代码：
/**
* 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:
int getheight(TreeNode* pointer)
{
if(pointer==NULL) return 0;
int leftnum=getheight(pointer->left);
if(leftnum==-1) return -1;
int rightnum=getheight(pointer->right);
if(rightnum==-1) return -1;
if(abs(rightnum-leftnum)>1) return -1;
else {
int res=1+max(leftnum,rightnum);
return res;
}
}
bool isBalanced(TreeNode* root) {
int res=getheight(root);
if(res!=-1)
{
return true;
}else {
return false;
}
}
};
LeetCode 257. 二叉树的所有路径
题目：
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
思路：
这道题采用中序遍历的方式，因为每条路径上面都要有根节点，所以每次遍历到叶子节点之后要回溯到根节点，之后再遍历另外一条路。回溯的过程用pop来模拟，当递归遍历到叶子节点的时候，path此时就已经记录了路径，所以在递归返回的时候就可以依次弹出。
代码：
/**
* 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:
void findall(TreeNode* cur, vector<int>& path, vector<string>& result)
{
path.push_back(cur->val);
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!=NULL)
{
findall(cur->left,path,result);
path.pop_back();
}
if(cur->right!=NULL)
{
findall(cur->right,path,result);
path.pop_back();
}
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<int> path;
vector<string> result;
if(root==NULL) return result;
findall(root,path,result);
return result;
}
};
LeetCode 404. 左叶子之和
题目：
给定二叉树的根节点 root ，返回所有左叶子之和。
思路：
采用后序遍历，这道题的难点在于如何找到并判断是左叶子节点。左叶子节点一方面是叶子节点，另一方面是左节点，如果直接遍历到了叶子节点，想要判断是否为左节点就存在一定的困难，所以直接遍历到叶子节点的父节点即可，如果该节点的子节点的左右节点均为空，那么说明就是叶子节点，再返回该节点的左节点就得到了左叶子节点。
代码：
/**
* 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:
int leftsum(TreeNode* pointer)
{
if(pointer==NULL)return 0;
int leftnum=leftsum(pointer->left);
if(pointer->left!=NULL&&pointer->left->left==NULL&&pointer->left->right==NULL)
{
leftnum= pointer->left->val;
}
int rightnum=leftsum(pointer->right);
int sum=leftnum+rightnum;
return sum;
}
int sumOfLeftLeaves(TreeNode* root) {
return leftsum(root);
}
};
