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) { //如果为空，则必定返回0 if(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; }

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

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

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