LeetCode：二叉树

文章目录572.另一棵树的子树662.二叉树最大宽度129.求根节点到叶子节点数字之和102.二叉树的层序遍历572.另一棵树的子树给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在返回 true 否则返回 false 。二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。【思路】如果root所在树和subRoot所在树完全相同则直接返回true否则就分别判断root的左子树和右子树是否和subRoot所在树完全相同classSolution{public:boolisSametree(TreeNode*p,TreeNode*q){if(pnullptrqnullptr)returntrue;//终止条件if(pqp-valq-val){returnisSametree(p-left,q-left)isSametree(p-right,q-right);}else{returnfalse;//终止条件}}boolisSubtree(TreeNode*root,TreeNode*subRoot){if(!root){returnfalse;//终止条件}if(isSametree(root,subRoot)){returntrue;//终止条件}returnisSubtree(root-left,subRoot)||isSubtree(root-right,subRoot);}};662.二叉树最大宽度给你一棵二叉树的根节点 root 返回树的 最大宽度 。树的 最大宽度 是所有层中最大的 宽度 。每一层的 宽度 被定义为该层最左和最右的非空节点即两个端点之间的长度。将这个二叉树视作与满二叉树结构相同两端点间会出现一些延伸到这一层的 null 节点这些 null 节点也计入长度。【思路】完全二叉树节点编号特性根id左孩子2id右孩子2id1DFS遍历时记录每层第一个访问到的最左节点编号到vec不断更细最大值当前节点编号- 本层最左编号 1classSolution{private:intmaxW0;vectorintfirstIds;public:intwidthOfBinaryTree(TreeNode*root){dfs(root,1,0);returnmaxW;}voiddfs(TreeNode*node,intid,intdepth){if(nodenullptr)return;// 第一次到达这一层记录最左节点编号if(firstIds.size()depth){firstIds.push_back(id);}// 更新最大宽度maxWmax(maxW,id-firstIds[depth]1);// 遍历左右子树dfs(node-left,id*2,depth1);dfs(node-right,id*21,depth1);}};129.求根节点到叶子节点数字之和给你一个二叉树的根节点 root 树中每个节点都存放有一个 0 到 9 之间的数字。每条从根节点到叶节点的路径都代表一个数字例如从根节点到叶节点的路径 1 - 2 - 3 表示数字 123 。计算从根节点到叶节点生成的 所有数字之和 。叶节点 是指没有子节点的节点。【思路】dfs深度优先遍历preSum * 10 node-val乘10是关键classSolution{public:intdfs(TreeNode*root,intpreSum){if(rootnullptr)return0;intsumpreSum*10root-val;//核心!if(root-leftnullptrroot-rightnullptr){returnsum;}else{returndfs(root-left,sum)dfs(root-right,sum);}}intsumNumbers(TreeNode*root){returndfs(root,0);}};102.二叉树的层序遍历给你二叉树的根节点 root 返回其节点值的 层序遍历 。 即逐层地从左到右访问所有节点【思路】queue存放节点怎么区分每层BFS循环当队列queue为空时跳出建立一个临时vector用于存储当前层数据循环当前层循环次数为当前层的节点数!!!核心- 出队列首元素出队即为node- tmp存储- 添加子节点若node的左右子节点不为空则将其加入队列queue