一、平衡二叉树
平衡二叉树的定义:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
使用递归方式:首先需要知道高度是什么意思,怎么获取高度。如果高度差大于1了,那么回复高度就没有意义了。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
int getHight(struct TreeNode* root)//得到左右子树的高度差
{
if(root == NULL)
{
return 0;
}
int left_len = getHight(root->left);
if(left_len == -1) return -1;
int right_len = getHight(root->right);
if(right_len == -1) return -1;
return abs(right_len - left_len) > 1? -1 : 1 + (right_len > left_len? right_len : left_len);
}
bool isBalanced(struct TreeNode* root) {
if(root == NULL)
{
return true;
}
int len = getHight(root);
return len == -1? false : true;
}
二、二叉树所有路径
主要是理解递归+回溯的思路,每一次递归之后,需要回退,把路径搜索完成,遍历一个完整的路径。解答过程遇到两个方面的问题:
1 就是打印函数,sprintf使用不当,导致保存出错;之前使用的数字转字符函数和strcat,没使用成功;
2 就是c语言写法,需要传入top在里面,因此按照代码随想录的思路,先把value入栈,top在递归过程,会变化,导致元素缺失,因此需要把入栈操作放到判断左右子树的条件里面。
#define ARRNUM 101
void trans(struct TreeNode* curNode, char** result, int* stk, int* returnSize, int top)
{
//stk[top++] = curNode->val;//stack push
//printf(" %d -> %d\n", top, stk[top]);
// if(curNode == NULL)
// return;
if(curNode->left == NULL && curNode->right == NULL)
{
int len = 0;
for(int i = 0; i < top; i++)//top is "0" index start
{
len += sprintf(result[(*returnSize)] + len, "%d->", stk[i]);
//printf("val = %d\n",stk[i]);
}
//printf("top = %d\n", top);
sprintf(result[(*returnSize)] + len, "%d", curNode->val);
(*returnSize)++;//push到result
return;
}
if(curNode->left)
{
stk[top++] = curNode->val;
trans(curNode->left, result, stk, returnSize, top);
--top;//value stack pop
//printf("/top = %d\n", top);
}
if(curNode->right)
{
stk[top++] = curNode->val;
trans(curNode->right, result, stk, returnSize, top);
--top;//value stack pop
//printf("//top = %d\n", top);
}
}
char** binaryTreePaths(struct TreeNode* root, int* returnSize) {
/**定义字符数组**/
char** result = (char**)malloc(sizeof(char*) * ARRNUM);//定义100个字符串
for(int i = 0; i < ARRNUM; i++)
{
result[i] = (char*)malloc(ARRNUM);//每个字符串定义100长度
}
*returnSize = 0;
if(root == NULL)
return result;
/**定义保存节点值的数组模拟栈**/
int* stack = (int*)malloc(sizeof(int) * 1024);
int top = 0;//栈的位置
trans(root, result, stack, returnSize, top);
return result;
}
三、左叶子之和
重点是理解左叶子节点的含义:节点A的左孩子不为空,且左孩子的左右孩子都为空(说明是叶子节点),那么A节点的左孩子为左叶子节点(代码随想录的解释)
int sumOfLeftLeaves(struct TreeNode* root){
//递归出口
if(root == NULL)
return 0;
if(root->left == NULL && root->right == NULL)//没有左y右子树, 不存在左叶子节点
return 0;
int leftvalue = sumOfLeftLeaves(root->left);
if(root->left && root->left->left == NULL && root->left->right ==NULL)
{
leftvalue = root->left->val;//保存当前叶子节点的值
}
//右子树的左叶子节点
int rightvalue = sumOfLeftLeaves(root->right);
return leftvalue + rightvalue;
}