上海网站建设模版,网站标题名字和备案名字,c 网站开发 调试,上海网络营销推广服务二叉树的最大深度
二叉树中和为某一值的路径(一)
二叉搜索树与双向链表
对称的二叉树 二叉树的最大深度 描述 求给定二叉树的最大深度#xff0c; 深度是指树的根节点到任一叶子节点路径上节点的数量。 最大深度是所有叶子节点的深度的最大值。 #xff08;注#xff1a;…二叉树的最大深度
二叉树中和为某一值的路径(一)
二叉搜索树与双向链表
对称的二叉树 二叉树的最大深度 描述 求给定二叉树的最大深度 深度是指树的根节点到任一叶子节点路径上节点的数量。 最大深度是所有叶子节点的深度的最大值。 注叶子节点是指没有子节点的节点。 【递归】
class Solution {
public:int maxDepth(TreeNode* root) {// write code hereif(rootnullptr)return 0;int left maxDepth(root-left);int right maxDepth(root-right);return leftright?left1:right1;}
};
【非递归】层序遍历(使用队列存储结点)
class Solution {
public:int maxDepth(TreeNode* root) {// write code hereif(root nullptr)return 0;int res 0;queueTreeNode* q;q.push(root);while(!q.empty()){int size q.size();while(size--){TreeNode* cur q.front();q.pop();if(cur-left) q.push(cur-left);if(cur-right) q.push(cur-right);}res;}return res;}
}; 二叉树中和为某一值的路径(一)
描述
给定一个二叉树root和一个值 sum 判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。
1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
2.叶子节点是指没有子节点的节点
3.路径只能从父节点到子节点不能从子节点到父节点
4.总节点数目为n 例如 给出如下的二叉树 sum22 sum22 返回true因为存在一条路径 5→4→11→25→4→11→2的节点值之和为 22
class Solution {
public:bool flag false;void dfs(TreeNode* root, int sum){if(rootnullptr)return;sum-root-val;if(sum0 root-leftnullptr root-rightnullptr){flag true; // 如果为根节点并且sum0那么存在路径return;}dfs(root-left, sum);dfs(root-right, sum);}bool hasPathSum(TreeNode* root, int sum) {dfs(root, sum);return flag;}
}; 二叉搜索树与双向链表 输入一棵二叉搜索树将该二叉搜索树转换成一个排序的双向链表。如下图所示 数据范围输入二叉树的节点数 0≤n≤10000≤n≤1000二叉树中每个节点的值 0≤val≤10000≤val≤1000 要求空间复杂度O(1)O(1)即在原树上操作时间复杂度 O(n)O(n) 注意: 1.要求不能创建任何新的结点只能调整树中结点指针的指向。当转化完成以后树中节点的左指针需要指向前驱树中节点的右指针需要指向后继 2.返回链表中的第一个节点的指针 3.函数返回的TreeNode有左右指针其实可以看成一个双向链表的数据结构 4.你不用输出双向链表程序会根据你的返回值自动打印输出 class Solution {
public:vectorTreeNode* res;void Inoder(TreeNode* root){if(root NULL)return;Inoder(root-left);res.push_back(root);Inoder(root-right);}TreeNode* Convert(TreeNode* pRootOfTree) {if(pRootOfTreeNULL)return NULL;Inoder(pRootOfTree);for(int i 0; i res.size()-1; i){res[i]-right res[i1];res[i1]-left res[i];}return res[0];}
};对称的二叉树
描述
给定一棵二叉树判断其是否是自身的镜像即是否对称 例如 下面这棵二叉树是对称的 下面这棵二叉树不对称。 数据范围节点数满足 0≤n≤10000≤n≤1000节点上的值满足 ∣val∣≤1000∣val∣≤1000 要求空间复杂度 O(n)O(n)时间复杂度 O(n)O(n) 备注 你可以用递归和迭代两种方法解决这个问题 【递归解法】
class Solution {
public:bool recursion(TreeNode* p, TreeNode* q){if(pnullptr qnullptr)return true;else if(pnullptr || qnullptr)return false;else if(q-val ! p-val)return false;return recursion(p-left, q-right) recursion(p-right, q-left);}bool isSymmetrical(TreeNode* root) {if(rootnullptr)return true;return recursion(root, root);}
};
【非递归】
class Solution {
public:bool isSymmetrical(TreeNode* root) {if(rootnullptr)return true;queueTreeNode* q1;queueTreeNode* q2;q1.push(root-left);q2.push(root-right);while(!q1.empty() !q2.empty()){TreeNode* left q1.front();TreeNode* right q2.front();q1.pop();q2.pop();if(leftnullptr rightnullptr)continue;if(leftnullptr || rightnullptr || left-val ! right-val)return false;q1.push(left-left);q1.push(left-right);q2.push(right-right);q2.push(right-left);}return true;}
};
