leetcode刷题第十三天——二叉树Ⅲ

本次刷题顺序是按照卡尔的代码随想录中给出的顺序

翻转二叉树

226. 翻转二叉树

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*//*总体思路就是，对于每一个结点，将其左右孩子结点对换*/struct TreeNode* invertTree(struct TreeNode* root) {if(root == NULL) return NULL;struct TreeNode* tmp;//交换左右子树tmp = root->left;root->left = root->right;root->right = tmp;//在对左右子树分别进行翻转root->left = invertTree(root->left);root->right = invertTree(root->right);return root;
}

对称二叉树

d101. 对称二叉树

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*//*总体思路，对于当前结点而言，其左孩子与右孩子的结点值相同*左孩子的(左、右)孩子的结点值与右孩子的(右、左)孩子的结点值相同*/bool isSymmetree(struct TreeNode* p, struct TreeNode* q) {if(p == NULL && q == NULL) return true;else if(p != NULL && q != NULL) {return (p->val == q->val && isSymmetree(p->left, q->right) \&& isSymmetree(p->right, q->left));}else {return false;}
}bool isSymmetric(struct TreeNode* root) {return isSymmetree(root->left, root->right);
}

相同的树

100. 相同的树

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*//*对于两棵树，相同则说明，对于两棵树中每个相应的结点，其值必须相同*结点的左、右孩子也必须完全相同*/bool isSameTree(struct TreeNode* p, struct TreeNode* q) {if(p == NULL && q == NULL) return true;else if(p != NULL && q != NULL) {return (p->val == q->val && isSameTree(p->right, q->right) \&& isSameTree(p->left, q->left));}else {return false;}
}

另一颗树的子树

572. 另一棵树的子树

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*//*建立在“判断两棵树是相同的树”的基础之上，*总体思路：如果以当前结点为根的树与指定树subRoot相同，则直接返回true*否则，分别查看以当前结点的左、右孩子结点为根的树与subRoot是否相同，有则返回true*否则，返回false*/bool isSameTree(struct TreeNode* p, struct TreeNode* q) {if(p == NULL && q == NULL) return true;else if(p != NULL && q != NULL) {return (p->val == q->val && isSameTree(p->left, q->left) && \isSameTree(p->right, q->right));}else return false;
}bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {if(isSameTree(root, subRoot)) return true;if(root != NULL) {return (isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot));}else return false;
}

二叉树的最大深度

104. 二叉树的最大深度

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*//*利用层序遍历的框架，即可统计最大深度，因为内层循环就是遍历一层的结点，外层循环就是遍历所有层，*故而，每进行依次外层循环，层数加1，跳出外层循环后，返回层数即为最大深度*/int maxDepth(struct TreeNode* root) {if(root == NULL) return 0;struct TreeNode** st = malloc(sizeof(struct TreeNode*) * 10001);struct TreeNode* tmp;int rear = -1, mid_rear, front = -1, sum = 0;st[++rear] = root;mid_rear = rear;while(rear != front) {while(mid_rear != front) {tmp = st[++front];//判断子树是否需要入队列if(tmp->left) st[++rear] = tmp->left;if(tmp->right) st[++rear] = tmp->right;}sum++;mid_rear = rear;}return sum;
}

二叉树的最小深度

111. 二叉树的最小深度

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*//*也是建立在层次遍历的基础之上，如果内层循环在遍历当前层结点时，*出现某个结点左、右子树均为NULL，则直接返回当前层的深度*/int minDepth(struct TreeNode* root) {if(root == NULL) return 0;struct TreeNode** st = malloc(sizeof(struct TreeNode*) * 100001);struct TreeNode* tmp;int rear = -1, mid_rear, front = -1, sum = 0;st[++rear] = root;mid_rear = rear;while(rear != front) {sum++;while(mid_rear != front) {tmp = st[++front];//判断子树是否需要入队列if(tmp->left) st[++rear] = tmp->left;if(tmp->right) st[++rear] = tmp->right;if(!tmp->left && !tmp->right) return sum;}mid_rear = rear;}return sum;
}

完全二叉树的结点个数

222. 完全二叉树的节点个数

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*//*利用满二叉树的性质进行求解*当前结点，如果左、右深度一致，说明是满二叉树，直接由公式得到节点数*如果左、右深度不一致，则返回左子树结点数+右子树结点数+1**为什么可以这么做？因为，完全二叉树除了最后一层未满，其它层均是满的*/int countNodes(struct TreeNode* root) {if(root == NULL) return 0;struct TreeNode* l_child = root->left, * r_child = root->right;int l_cnt = 0, r_cnt = 0;while(l_child != NULL) {l_cnt++;l_child = l_child->left;}while(r_child != NULL) {r_cnt++;r_child = r_child->right;}//若向左和向右遍历深度一致，说明是满二叉树，可以直接求解结点个数if(l_cnt == r_cnt) return (2  <<  l_cnt) - 1;else return (countNodes(root->left) + countNodes(root->right) + 1);
}

平衡二叉树

110. 平衡二叉树

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*//*对于每个结点，求其左右子树的高度*所有结点，左右子树高度差不应超过1*///求得树的高度
int treeDeepth(struct TreeNode* p) {if(p == NULL) return 0;else return fmax(treeDeepth(p->left), treeDeepth(p->right)) + 1;
}bool isBalanced(struct TreeNode* root) {if(root == NULL) return true;//对于当前结点，两棵子树的高度差小于等于1，则判断结点的左右子树是否为平衡二叉树if(fabs(treeDeepth(root->left) - treeDeepth(root->right)) <= 1) {return isBalanced(root->left) && isBalanced(root->right);}else return false;//对于当前结点，两棵子树的高度差大于1，则直接返回错误
}

左叶子之和

404. 左叶子之和

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
int sumOfLeftLeaves(struct TreeNode* root) {//如果为空，则必定返回0if(root == NULL) return 0;//如果当前结点的左孩子左右子树均为空，则当前结点的左孩子是左叶子if(root->left != NULL && root->left->left == NULL && root->left->right == NULL) {return root->left->val + sumOfLeftLeaves(root->right);}else {//如果当前结点左孩子为空，或者其左孩子左右子树不为空return sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);}
}

找树左下角的值

513. 找树左下角的值

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*//*找最左下结点的值，依照层次遍历的框架，最后一层的第一个结点就是最左下的结点*/int findBottomLeftValue(struct TreeNode* root) {struct TreeNode** qu = malloc(sizeof(struct TreeNode*) * 10000);struct TreeNode* tmp;int rear = -1, mid_rear, front = -1, res;qu[++rear] = root;do {mid_rear = rear;res = qu[front + 1]->val;while(front != mid_rear) {tmp = qu[++front];if(tmp->left) qu[++rear] = tmp->left;if(tmp->right) qu[++rear] = tmp->right;}}while(rear != front);return res;
}

最大二叉树

654. 最大二叉树

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*//*按照先序遍历的思想，先构造根节点，再构造左子树，最后构造右子树*需要配合查找数组最大值下标的程序进行构造*/int FindMaxIdx(int* nums, int start, int end) {int idx = start, max = INT_MIN, max_idx;while(idx <= end) {if(nums[idx] > max) {max = nums[idx];max_idx = idx;}idx++;}return max_idx;
}struct TreeNode* constructMaximumBinaryTree(int* nums, int numsSize) {if(numsSize == 0) return NULL;int max_idx = FindMaxIdx(nums, 0, numsSize - 1);struct TreeNode* root = malloc(sizeof(struct TreeNode));root->val = nums[max_idx];root->left = constructMaximumBinaryTree(nums, max_idx);root->right = constructMaximumBinaryTree(nums + max_idx + 1, numsSize - max_idx - 1);return root;
}

合并二叉树

617. 合并二叉树

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*//*在遍历过程中，两个结点均存在，则返回结点值为两者之和，*只有一者存在，直接返回该结点，*两者均不存在，则直接返回NULL*/struct TreeNode* mergeTrees(struct TreeNode* root1, struct TreeNode* root2) {if(root1 == NULL && root2 == NULL) return NULL;struct TreeNode* root = malloc(sizeof(struct TreeNode));if(root1 != NULL && root2 != NULL) {root->val = root1->val + root2->val;root->left = mergeTrees(root1->left, root2->left);root->right = mergeTrees(root1->right, root2->right);}else {if(root1 != NULL) {root = root1;}else root = root2;}return root;
}

递归用得挺多的，后面可以尝试迭代算法的实现。

递归需要考虑，递归的终止条件是什么？递归程序的单层逻辑是什么？

需要熟练掌握二叉树的四种遍历方式的框架，一般都是以此为突破口进行编程