网站开发与app开发的区别,动态广告怎么做出来的,网站建设水平,白酒营销网站题目引用 找树左下角的值路径总和从中序与后序遍历构造二叉树
今天就简简单单三道题吧~
1. 找到树左下角的值 给定一个二叉树的 根节点 root#xff0c;请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。 示例 1: 输入: root [2,1,3] 输出: 1 我们…题目引用 找树左下角的值路径总和从中序与后序遍历构造二叉树
今天就简简单单三道题吧~
1. 找到树左下角的值 给定一个二叉树的 根节点 root请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。 示例 1: 输入: root [2,1,3] 输出: 1 我们来分析一下题目最底层的叶子节点所以我们要求出树的深度并且进行判断他是否到达底层。首先我们定义一个全局变量res和全局变量maxDep来记录递归过程中更深的节点和更深节点的值。然后我们判断当前节点有没有左右孩子节点如果有我们递归进那个节点并更新res和maxDep同时定义局部变量depth将其后传进下一层当其操作完返回这一层时将depth--用作向右孩子递归的参数。而这个过程就叫做回溯。 我们来看代码
int res;int maxDepINT_MIN;void travisal(TreeNode* root,int depth){if(root-leftNULLroot-rightNULL){if(depthmaxDep){maxDepdepth;resroot-val;}return;}if(root-left){depth;travisal(root-left,depth);depth--;}if(root-right){depth;travisal(root-right,depth);depth--;}}int findBottomLeftValue(TreeNode* root) {travisal(root,0);return res;}2.路径总和 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径这条路径上所有节点值相加等于目标和 targetSum 。如果存在返回 true 否则返回 false 。
叶子节点 是指没有子节点的节点。 示例 1 输入root [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum 22 输出true 解释等于目标和的根节点到叶节点路径如上图所示。 我们来看题目这道题其实知道了原理就和上道题大差不差了。上一道题目是找到最底层的节点的值而这一道题目是找到一条相加为0的路径两道题目都需要我们在二叉树中一层一层的寻找符合条件的节点并且返回它那么我们是不是不难写出这样的模版
看情况返回类型 traversal(TreeNode* root,//第二变量用于判断){//对每一个节点要做的操作if(root-left){//增加条件//递归左边//减少条件}if(root-right){//增加条件//递归右边//减少条件}//考虑是否返回}那么我们在这道题就将相加改为一开始就有一个变量等于targetSum逐层减去每个节点的val一旦0就返回true。 来看代码
bool traversal(TreeNode* root,int count){if(!root-left!root-rightcount0) return true;if(!root-left!root-right) return false;if(root-left){count-root-left-val;if(traversal(root-left,count)) return true;countroot-left-val;}if(root-right){count-root-right-val;if(traversal(root-right,count)) return true;countroot-right-val;}return false;}bool hasPathSum(TreeNode* root, int targetSum) {if(rootNULL) return false;return traversal(root,targetSum-root-val);}大家看一旦我们整理出规律是不是这类题目我们只要考虑细节条件就能迎刃而解呢
3.从中序与后序遍历构造二叉树 给定两个整数数组 inorder 和 postorder 其中 inorder 是二叉树的中序遍历 postorder 是同一棵树的后序遍历请你构造并返回这颗 二叉树 。 示例 1: 输入inorder [9,3,15,20,7], postorder [9,15,7,20,3] 输出[3,9,20,null,null,15,7] 这道题目我们在学习数据结构时就做过现在只要模拟过程就能解决啦。直接看代码
TreeNode* traversal(vectorint inorder,vectorint postorder){if(postorder.size()0) return NULL;int rootValuepostorder[postorder.size()-1];TreeNode* rootnew TreeNode(rootValue);if(postorder.size()1) return root;int delimitIndex;for(delimitIndex0;delimitIndexinorder.size();delimitIndex){if(inorder[delimitIndex]rootValue) break;}vectorint leftInorder(inorder.begin(),inorder.begin()delimitIndex);vectorint rightInorder(inorder.begin()delimitIndex1,inorder.end());postorder.resize(postorder.size()-1);vectorint leftPostorder(postorder.begin(),postorder.begin()leftInorder.size());vectorint rightPostorder(postorder.begin()leftInorder.size(),postorder.end());root-lefttraversal(leftInorder,leftPostorder);root-righttraversal(rightInorder,rightPostorder);return root;}TreeNode* buildTree(vectorint inorder, vectorint postorder) {if (inorder.size() 0 || postorder.size() 0) return NULL;return traversal(inorder, postorder);}总结 今天的题目其实就是昨天的拓展与提升大家务必将昨天的消化了再来做今天的题目。
