一、二叉树介绍二叉树是最常用的树形结构特别适合编码常常将一般的树转换为二叉树来处理。二叉树的每个节点最多有两个子节点分别称为左孩子、右孩子以它们为根的子树称为左子树、右子树。二叉树的每层节点数以2的倍数递增所以二叉树的第i层最多有2i−12^{i - 1}2i−1个节点。如果每层的节点数都是满的称它为满二叉树。一个n层的满二叉树一共有2”一1个节点。如果满二叉树只在最后一层有缺失并且缺失的编号都在最后则称为完全二叉树。二、二叉树的特点二叉树之所以应用广泛得益于它的形态。高级数据结构大部分与二叉树有关下面列举二叉树的一些优势。(1)在二叉树上能进行极高效率的访问。一棵平衡的二叉树如满二叉树或完全二叉树每层的节点数量约为上一层数量的2倍。也就是说一棵有N个节点的满二叉树树的高度为O(log2Nlog_2Nlog2N)。从根节点到叶子节点只需要走log2Nlog_2Nlog2N步就能到达树中的任意节点。例如N100万树的高度仅为log2Nlog_2Nlog2N,只需要20步就能到达这100万个节点中的任意一个。但是如果二叉树不是满的而且很不平衡甚至在极端情况下退化为一条“链”访问效率会打折扣。所以维护二叉树的平衡是高级数据结构的主要任务之一。(2)二叉树很适合做从整体到局部、从局部到整体的操作。二叉树内的一棵子树可以看作整棵树的一个子区间求区间最值、区间和、区间翻转、区间合并、区间分裂等用二叉树都很快捷。例如文本编辑器用二叉树实现效率很高。(3)基于二叉树的算法容易设计和实现。例如二叉树用宽度优先搜索Breadth-First Search,BFS)和深度优先搜索(Depth-First Search,DFS)处理都极为简便。二叉树可以一层一层地搜索这是BFS。二叉树的任意一个子节点是以它为根的一棵二叉树这是一种递归结构用DFS访问二叉树极容易编码。BFS和DFS是二叉树的绝配。三、二叉树的遍历二叉树的遍历是指按某条搜索路径访问树中每个结点使得每个结点均被访问一次而且仅被访问一次。由于二叉树是一种非线性结构每个结点都可能有两棵子树因而需要寻找一种规律以便使二叉树上的结点能排列在一个线性队列上进而便于遍历。由二叉树的递归定义可知遍历一棵二叉树便要决定对根结点N、左子树L和右子树R的访问顺序。按照先遍历左子树再遍历右子树的原则常见的遍历次序有先序(NLR)、中序(LNR)和后序(LRN)三种遍历算法其中“序”指的是根结点在何时被访问。递归方法遍历二叉树先序遍历voidPreorder(BiTree T){if(T!NULL){visit(T);//访问根结点Preorder(T-lchild);//递归遍历左子树Preorder(T-rchild);//递归遍历右子树}}中序遍历voidPreorder(BiTree T){if(T!NULL){Preorder(T-lchild);//递归遍历左子树visit(T);//访问根结点Preorder(T-rchild);//递归遍历右子树}}后序遍历voidPreorder(BiTree T){if(T!NULL){Preorder(T-lchild);//递归遍历左子树Preorder(T-rchild);//递归遍历右子树visit(T);//访问根结点}}三种遍历算法中递归遍历左、右子树的顺序都是固定的只是访问根结点的顺序不同。不管采用哪种遍历算法每个结点都访问一次且仅访问一次故时间复杂度都是O(n)。在递归遍历中递归工作栈的栈深恰好为树的深度所以在最坏情况下二叉树是有个结点且深度为n的单支树遍历算法的空间复杂度为O(n)。迭代方法遍历二叉树前序遍历classSolution{public:vectorintinorderTraversal(TreeNode*root){vectorintans;TreeNode*curroot,*prenullptr;stackTreeNode*s;while(cur||s.size()){if(cur){s.push(cur);curcur-left;}else{curs.top();s.pop();ans.push_back(cur-val);curcur-right;}}returnans;}};后序遍历算法思想后序非递归遍历二叉树是先访问左子树再访问右子树最后访问根结点。必须分清返回时是从左子树返回的还是从右子树返回的因此设定一个辅助指针r用于指向最近访问过的结点。也可在结点中增加一个标志域记录是否已被访问。classSolution{public:vectorintpostorderTraversal(TreeNode*root){vectorintans;TreeNode*curroot;TreeNode*pre;stackTreeNode*s;while(cur||s.size()){if(cur){s.push(cur);curcur-left;}else{curs.top();//判断现在是从左子树返回还是从右子树返回if(cur-rightcur-right!pre){curcur-right;}else{ans.push_back(cur-val);s.pop();precur;curnullptr;//保证cur返回因为当前节点的左右子树均访问完}}}returnans;}};四、二叉树的性质4.1 lc104. 二叉树的最大深度classSolution{public:intmaxDepth(TreeNode*root){if(rootnullptr){return0;}returnmax(maxDepth(root-left),maxDepth(root-right))1;}};4.2 lc 543. 二叉树的直径题目描述给你一棵二叉树的根节点返回该树的直径。二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点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) {} * }; */classSolution{public:intans0;intdiameterOfBinaryTree(TreeNode*root){if(!root)return0;depth(root);returnans;}intdepth(TreeNode*root){if(!root)return0;intldepth(root-left),rdepth(root-right);ansmax(ans,lr);//该树经过当前节点的最长路径returnmax(l,r)1;//以当前节点为根的子树高度}};4.3 lc 101. 对称二叉树递归做法二叉树某个节点的两个子树对称当且仅当两个子树的根节点值相等第一棵子树的左子树和第二棵子树的右子树互为镜像且第一棵子树的右子树和第二棵子树的左子树互为镜像classSolution{public:boolisSymmetric(TreeNode*root){return!root||dfs(root-left,root-right);}booldfs(TreeNode*l,TreeNode*r){if(!l||!r)return!l!r;elsereturnl-valr-valdfs(l-left,r-right)dfs(l-right,r-left);}};时间复杂度分析从上到下每个节点仅被遍历一遍所以时间复杂度是 O(n)。4.4 lc236 二叉树的最近公共祖先给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。思路在类中设置一个变量flag如果在递归过程中第一次有一个节点同时收到了左子树和右子树的true标志说明该节点是公共祖先。节点自身可以作为自己的祖先这一点你怎么判断如何分析另一个节点应该从左子树而来还是右子树而来这种情况遇到空子树怎么办解决直接使用数字代表不要使用布尔变量。要不然需要自身一个左子树一个右子树一个三个布尔变量参与判断增大编码复杂度。使用一个数字变量获得一个条件满足其数量加一。/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */classSolution{public:TreeNode*ansNULL;TreeNode*lowestCommonAncestor(TreeNode*root,TreeNode*p,TreeNode*q){dfs(root,p,q);returnans;}booldfs(TreeNode*root,TreeNode*p,TreeNode*q){if(rootNULL||ans!NULL)returnfalse;intflag0;if(root-valp-val||root-valq-val)flag;if(dfs(root-left,p,q))flag;if(dfs(root-right,p,q))flag;if(flag){if(flag2)ansroot;returntrue;}returnfalse;}};时间复杂度O(N)其中 N 是二叉树的节点数。二叉树的所有节点有且只会被访问一次因此时间复杂度为 O(N)。空间复杂度O(N) 其中 N 是二叉树的节点数。递归调用的栈深度取决于二叉树的高度二叉树最坏情况下为一条链此时高度为 N因此空间复杂度为 O(N)。递归判断整棵子树递归判断左子树和右子树有没有节点pq当我们第一次搜到当前节点子树中既有p又有q该节点一定是p和q的最近公共祖先。
【数据结构】二叉树
一、二叉树介绍二叉树是最常用的树形结构特别适合编码常常将一般的树转换为二叉树来处理。二叉树的每个节点最多有两个子节点分别称为左孩子、右孩子以它们为根的子树称为左子树、右子树。二叉树的每层节点数以2的倍数递增所以二叉树的第i层最多有2i−12^{i - 1}2i−1个节点。如果每层的节点数都是满的称它为满二叉树。一个n层的满二叉树一共有2”一1个节点。如果满二叉树只在最后一层有缺失并且缺失的编号都在最后则称为完全二叉树。二、二叉树的特点二叉树之所以应用广泛得益于它的形态。高级数据结构大部分与二叉树有关下面列举二叉树的一些优势。(1)在二叉树上能进行极高效率的访问。一棵平衡的二叉树如满二叉树或完全二叉树每层的节点数量约为上一层数量的2倍。也就是说一棵有N个节点的满二叉树树的高度为O(log2Nlog_2Nlog2N)。从根节点到叶子节点只需要走log2Nlog_2Nlog2N步就能到达树中的任意节点。例如N100万树的高度仅为log2Nlog_2Nlog2N,只需要20步就能到达这100万个节点中的任意一个。但是如果二叉树不是满的而且很不平衡甚至在极端情况下退化为一条“链”访问效率会打折扣。所以维护二叉树的平衡是高级数据结构的主要任务之一。(2)二叉树很适合做从整体到局部、从局部到整体的操作。二叉树内的一棵子树可以看作整棵树的一个子区间求区间最值、区间和、区间翻转、区间合并、区间分裂等用二叉树都很快捷。例如文本编辑器用二叉树实现效率很高。(3)基于二叉树的算法容易设计和实现。例如二叉树用宽度优先搜索Breadth-First Search,BFS)和深度优先搜索(Depth-First Search,DFS)处理都极为简便。二叉树可以一层一层地搜索这是BFS。二叉树的任意一个子节点是以它为根的一棵二叉树这是一种递归结构用DFS访问二叉树极容易编码。BFS和DFS是二叉树的绝配。三、二叉树的遍历二叉树的遍历是指按某条搜索路径访问树中每个结点使得每个结点均被访问一次而且仅被访问一次。由于二叉树是一种非线性结构每个结点都可能有两棵子树因而需要寻找一种规律以便使二叉树上的结点能排列在一个线性队列上进而便于遍历。由二叉树的递归定义可知遍历一棵二叉树便要决定对根结点N、左子树L和右子树R的访问顺序。按照先遍历左子树再遍历右子树的原则常见的遍历次序有先序(NLR)、中序(LNR)和后序(LRN)三种遍历算法其中“序”指的是根结点在何时被访问。递归方法遍历二叉树先序遍历voidPreorder(BiTree T){if(T!NULL){visit(T);//访问根结点Preorder(T-lchild);//递归遍历左子树Preorder(T-rchild);//递归遍历右子树}}中序遍历voidPreorder(BiTree T){if(T!NULL){Preorder(T-lchild);//递归遍历左子树visit(T);//访问根结点Preorder(T-rchild);//递归遍历右子树}}后序遍历voidPreorder(BiTree T){if(T!NULL){Preorder(T-lchild);//递归遍历左子树Preorder(T-rchild);//递归遍历右子树visit(T);//访问根结点}}三种遍历算法中递归遍历左、右子树的顺序都是固定的只是访问根结点的顺序不同。不管采用哪种遍历算法每个结点都访问一次且仅访问一次故时间复杂度都是O(n)。在递归遍历中递归工作栈的栈深恰好为树的深度所以在最坏情况下二叉树是有个结点且深度为n的单支树遍历算法的空间复杂度为O(n)。迭代方法遍历二叉树前序遍历classSolution{public:vectorintinorderTraversal(TreeNode*root){vectorintans;TreeNode*curroot,*prenullptr;stackTreeNode*s;while(cur||s.size()){if(cur){s.push(cur);curcur-left;}else{curs.top();s.pop();ans.push_back(cur-val);curcur-right;}}returnans;}};后序遍历算法思想后序非递归遍历二叉树是先访问左子树再访问右子树最后访问根结点。必须分清返回时是从左子树返回的还是从右子树返回的因此设定一个辅助指针r用于指向最近访问过的结点。也可在结点中增加一个标志域记录是否已被访问。classSolution{public:vectorintpostorderTraversal(TreeNode*root){vectorintans;TreeNode*curroot;TreeNode*pre;stackTreeNode*s;while(cur||s.size()){if(cur){s.push(cur);curcur-left;}else{curs.top();//判断现在是从左子树返回还是从右子树返回if(cur-rightcur-right!pre){curcur-right;}else{ans.push_back(cur-val);s.pop();precur;curnullptr;//保证cur返回因为当前节点的左右子树均访问完}}}returnans;}};四、二叉树的性质4.1 lc104. 二叉树的最大深度classSolution{public:intmaxDepth(TreeNode*root){if(rootnullptr){return0;}returnmax(maxDepth(root-left),maxDepth(root-right))1;}};4.2 lc 543. 二叉树的直径题目描述给你一棵二叉树的根节点返回该树的直径。二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点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) {} * }; */classSolution{public:intans0;intdiameterOfBinaryTree(TreeNode*root){if(!root)return0;depth(root);returnans;}intdepth(TreeNode*root){if(!root)return0;intldepth(root-left),rdepth(root-right);ansmax(ans,lr);//该树经过当前节点的最长路径returnmax(l,r)1;//以当前节点为根的子树高度}};4.3 lc 101. 对称二叉树递归做法二叉树某个节点的两个子树对称当且仅当两个子树的根节点值相等第一棵子树的左子树和第二棵子树的右子树互为镜像且第一棵子树的右子树和第二棵子树的左子树互为镜像classSolution{public:boolisSymmetric(TreeNode*root){return!root||dfs(root-left,root-right);}booldfs(TreeNode*l,TreeNode*r){if(!l||!r)return!l!r;elsereturnl-valr-valdfs(l-left,r-right)dfs(l-right,r-left);}};时间复杂度分析从上到下每个节点仅被遍历一遍所以时间复杂度是 O(n)。4.4 lc236 二叉树的最近公共祖先给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。思路在类中设置一个变量flag如果在递归过程中第一次有一个节点同时收到了左子树和右子树的true标志说明该节点是公共祖先。节点自身可以作为自己的祖先这一点你怎么判断如何分析另一个节点应该从左子树而来还是右子树而来这种情况遇到空子树怎么办解决直接使用数字代表不要使用布尔变量。要不然需要自身一个左子树一个右子树一个三个布尔变量参与判断增大编码复杂度。使用一个数字变量获得一个条件满足其数量加一。/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */classSolution{public:TreeNode*ansNULL;TreeNode*lowestCommonAncestor(TreeNode*root,TreeNode*p,TreeNode*q){dfs(root,p,q);returnans;}booldfs(TreeNode*root,TreeNode*p,TreeNode*q){if(rootNULL||ans!NULL)returnfalse;intflag0;if(root-valp-val||root-valq-val)flag;if(dfs(root-left,p,q))flag;if(dfs(root-right,p,q))flag;if(flag){if(flag2)ansroot;returntrue;}returnfalse;}};时间复杂度O(N)其中 N 是二叉树的节点数。二叉树的所有节点有且只会被访问一次因此时间复杂度为 O(N)。空间复杂度O(N) 其中 N 是二叉树的节点数。递归调用的栈深度取决于二叉树的高度二叉树最坏情况下为一条链此时高度为 N因此空间复杂度为 O(N)。递归判断整棵子树递归判断左子树和右子树有没有节点pq当我们第一次搜到当前节点子树中既有p又有q该节点一定是p和q的最近公共祖先。