二叉树相关算法
二叉树相关性质：
性质一：在二叉树的第i层上至多有2^(i-1)个结点(i>=1)
性质二：深度为k的二叉树至多有2^(k-1)个结点(k>=1)
性质三：对任意一颗二叉树T，若终端结点数为n0，而其度数为2的结点数为n2，则n0=n2+1.
性质四：具有n个结点的完全二叉树的深度为 ⌊log n⌋+1(以2为底)
满二叉树：深度为k，且有2^(k-1)个结点的二叉树。 在满二叉树中，每层结点都是满的，即每层节点都具有最大结点数。
完全二叉树：深度为k，结点数为n的二叉树，如果其结点1n的位置序号分别于满二叉树的节点1n的位置序号一一对应，则为完全二叉树。可见，满二叉树必为完全二叉树，而完全二叉树不一定是满二叉树。
题目
二叉树的镜像
典型题例：
输入一个二叉树，将它变换为它的镜像。
示例 ：
输入树： 8 / \ 6 10 / \ / \ 5 7 9 11 [8,6,10,5,7,9,11,null,null,null,null,null,null,null,null] 输出树： 8 / \ 10 6 / \ / \ 11 9 7 5 [8,10,6,11,9,7,5,null,null,null,null,null,null,null,null]
思路
核心：
我们可以发现镜像后的树就是将原树的所有节点的左右儿子互换！
所以我们递归遍历原树的所有节点，将每个节点的左右儿子互换即可。
代码：
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: void mirror(TreeNode* root) { //判断参数 if (!root) return; swap(root->left, root->right); //交换左右子树 mirror(root->left); //递归遍历 mirror(root->right); } };
对称的二叉树
典型题例：
请实现一个函数，用来判断一棵二叉树是不是对称的。
如果一棵二叉树和它的镜像一样，那么它是对称的。
示例 ：
如下图所示二叉树[1,2,2,3,4,4,3,null,null,null,null,null,null,null,null]为对称二叉树： 1 / \ 2 2 / \ / \ 3 4 4 3 如下图所示二叉树[1,2,2,null,4,4,3,null,null,null,null,null,null]不是对称二叉树： 1 / \ 2 2 \ / \ 4 4 3
思路
递归判断两个子树是否互为镜像。
两个子树互为镜像当且仅当：
- 两个子树的根节点值相等；
- 第一棵子树的左子树和第二棵子树的右子树互为镜像，且第一棵子树的右子树和第二棵子树的左子树互为镜像；
代码：
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool isSymmetric(TreeNode* root) { if (!root) return true; //判断参数 return dfs (root->left, root->right); } bool dfs(TreeNode* p, TreeNode* q){ if (!p || !q) return !p && !q; //当p,q其中一个为空时,只有当p,q都为空返回true if (p->val != q->val) return false; //值不相等为false return dfs (p->left, q->right) && dfs (p->right, q->left); //递归遍历左右孩子 } };
充电站
推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习
