赞
踩
题述:
给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。
示例1:
输入:root = [3,9,20,null,null,15,7]
输出:[[3],[9,20],[15,7]]
示例 2:
输入:root = [1]
输出:[[1]]
示例 3:
输入: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) {} * }; */ class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> result; queue<TreeNode*> que; if(root) { que.push(root); } while(!que.empty()) { int size=que.size(); vector<int> vec; for(int i=0;i<size;i++) { TreeNode* node=que.front(); que.pop(); vec.push_back(node->val); if(node->left) { que.push(node->left); } if(node->right) { que.push(node->right); } } result.push_back(vec); } return result; } };
给你二叉树的根节点 root ,返回其节点值 自底向上的层序遍历 。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
示例 1:
输入:root = [3,9,20,null,null,15,7]
输出:[[15,7],[9,20],[3]]
示例 2:
输入:root = [1]
输出:[[1]]
示例 3:
输入: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) {} * }; */ class Solution { public: vector<vector<int>> levelOrderBottom(TreeNode* root) { vector<vector<int>> result; queue<TreeNode*> que; if(root) { que.push(root); } while(!que.empty()) { int size=que.size(); vector<int> vec; for(int i=0;i<size;i++) { TreeNode* node=que.front(); que.pop(); vec.push_back(node->val); if(node->left) { que.push(node->left); } if(node->right) { que.push(node->right); } } result.push_back(vec); } reverse(result.begin(),result.end()); return result; } };
给定一个二叉树的 根节点 root,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。
示例 1:
输入: [1,2,3,null,5,null,4]
输出: [1,3,4]
示例 2:
输入: [1,null,3]
输出: [1,3]
示例 3:
输入: []
输出: []
/** * 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) {} * }; */ class Solution { public: vector<int> rightSideView(TreeNode* root) { vector<int> result; queue<TreeNode*> que; if(root) { que.push(root); } while(!que.empty()) { int size=que.size(); for(int i=0;i<size;i++) { TreeNode* node=que.front(); que.pop(); if(i==size-1) { result.push_back(node->val); } if(node->left) { que.push(node->left); } if(node->right) { que.push(node->right); } } } return result; } };
题述:
给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
示例 1:
输入:root = [3,9,20,null,null,15,7]
输出:[3.00000,14.50000,11.00000]
解释:第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
因此返回 [3, 14.5, 11] 。
示例 2:
输入:root = [3,9,20,15,7]
输出:[3.00000,14.50000,11.00000]
C++实现:
/** * 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) {} * }; */ class Solution { public: vector<double> averageOfLevels(TreeNode* root) { vector<double> result; queue<TreeNode*> que; if(root) { que.push(root); } while(!que.empty()) { int size=que.size(); double sum=0; for(int i=0;i<size;i++) { TreeNode* node=que.front(); que.pop(); sum+=node->val; if(node->left) { que.push(node->left); } if(node->right) { que.push(node->right); } } sum=sum/size; result.push_back(sum); } return result; } };
给定一个 N 叉树,返回其节点值的层序遍历。(即从左到右,逐层遍历)。
树的序列化输入是用层序遍历,每组子节点都由 null 值分隔(参见示例)。
示例 1:
输入:root = [1,null,3,2,4,null,5,6]
输出:[[1],[3,2,4],[5,6]]
示例 2:
输入:root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出:[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]
/* // Definition for a Node. class Node { public: int val; vector<Node*> children; Node() {} Node(int _val) { val = _val; } Node(int _val, vector<Node*> _children) { val = _val; children = _children; } }; */ class Solution { public: vector<vector<int>> levelOrder(Node* root) { vector<vector<int>> result; queue<Node*> que; if(root) { que.push(root); } while(!que.empty()) { int size=que.size(); vector<int> vec; for(int i=0;i<size;i++) { Node* node=que.front(); que.pop(); vec.push_back(node->val); for(int i=0;i<node->children.size();i++) { if(node->children[i]) { que.push(node->children[i]); } } } result.push_back(vec); } return result; } };
题述:
给定一棵二叉树的根节点 root ,请找出该二叉树中每一层的最大值。
示例1:
输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]
示例2:
输入: root = [1,2,3]
输出: [1,3]
/** * 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) {} * }; */ class Solution { public: vector<int> largestValues(TreeNode* root) { vector<int> result; queue<TreeNode*> que; if(root) { que.push(root); } while(!que.empty()) { int size=que.size(); int maxValue=INT_MIN; for(int i=0;i<size;i++) { TreeNode* node=que.front(); que.pop(); maxValue=node->val>maxValue?node->val:maxValue; if(node->left) { que.push(node->left); } if(node->right) { que.push(node->right); } } result.push_back(maxValue); } return result; } };
leetcode 116. 填充每个节点的下一个右侧节点指针
题述:
给定一个 完美二叉树 ,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。
初始状态下,所有 next 指针都被设置为 NULL。
示例 1:
输入:root = [1,2,3,4,5,6,7]
输出:[1,#,2,3,#,4,5,6,7,#]
解释:给定二叉树如图 A 所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点,如图 B 所示。序列化的输出按层序遍历排列,同一层节点由 next 指针连接,‘#’ 标志着每一层的结束。
示例 2:
输入:root = []
输出:[]
C++代码实现:
/* // Definition for a Node. class Node { public: int val; Node* left; Node* right; Node* next; Node() : val(0), left(NULL), right(NULL), next(NULL) {} Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {} Node(int _val, Node* _left, Node* _right, Node* _next) : val(_val), left(_left), right(_right), next(_next) {} }; */ class Solution { public: Node* connect(Node* root) { queue<Node*> que; if(root) { que.push(root); } while(!que.empty()) { int size=que.size(); Node* node; Node* nodePre; for(int i=0;i<size;i++) { if(i==0) { nodePre=que.front(); que.pop(); node=nodePre; } else { node=que.front(); que.pop(); nodePre->next=node; nodePre=nodePre->next; } if(node->left) { que.push(node->left); } if(node->right) { que.push(node->right); } nodePre->next=NULL; } } return root; } };
leetcode 117. 填充每个节点的下一个右侧节点指针 II
给定一个二叉树
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。
示例 1:
输入:root = [1,2,3,4,5,6,7]
输出:[1,#,2,3,#,4,5,6,7,#]
解释:给定二叉树如图 A 所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点,如图 B 所示。序列化的输出按层序遍历排列,同一层节点由 next 指针连接,‘#’ 标志着每一层的结束。
示例 2:
输入:root = []
输出:[]
C++代码实现如下:
/* // Definition for a Node. class Node { public: int val; Node* left; Node* right; Node* next; Node() : val(0), left(NULL), right(NULL), next(NULL) {} Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {} Node(int _val, Node* _left, Node* _right, Node* _next) : val(_val), left(_left), right(_right), next(_next) {} }; */ class Solution { public: Node* connect(Node* root) { queue<Node*> que; if(root) { que.push(root); } while(!que.empty()) { int size=que.size(); Node* nodePre; Node* node; for(int i=0;i<size;i++) { if(i==0) { nodePre=que.front(); que.pop(); node=nodePre; } else { node=que.front(); que.pop(); nodePre->next=node; nodePre=nodePre->next; } if(node->left) { que.push(node->left); } if(node->right) { que.push(node->right); } } nodePre->next=NULL; } return root; } };
leetcode 104. 二叉树的最大深度
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
返回它的最大深度 3 。
C++递归:
/** * 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) {} * }; */ class Solution { public: int maxDepth(TreeNode* root) { //递归 if(root==NULL) { return 0; } int leftMaxDepth=maxDepth(root->left); int rightMaxDepth=maxDepth(root->right); return leftMaxDepth>rightMaxDepth?leftMaxDepth+1:rightMaxDepth+1; } };
C++非递归:
/** * 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) {} * }; */ class Solution { public: int maxDepth(TreeNode* root) { if(root==NULL) { return 0; } int depth=0; queue<TreeNode*> que; que.push(root); while(!que.empty()) { int size=que.size(); depth++; for(int i=0;i<size;i++) { TreeNode* node=que.front(); que.pop(); if(node->left) { que.push(node->left); } if(node->right) { que.push(node->right); } } } return depth; } };
题述:
给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明:叶子节点是指没有子节点的节点。
示例 1:
输入:root = [3,9,20,null,null,15,7]
输出:2
示例 2:
输入:root = [2,null,3,null,4,null,5,null,6]
输出:5
/** * 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) {} * }; */ class Solution { public: int minDepth(TreeNode* root) { if(root==NULL) { return 0; } if(root->left==NULL && root->right) { return 1+minDepth(root->right); } if(root->left && root->right==NULL) { return 1+minDepth(root->left); } return 1+min(minDepth(root->left),minDepth(root->right)); } };
C++非递归:
/** * 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) {} * }; */ class Solution { public: int minDepth(TreeNode* root) { queue<TreeNode*> que; if(root==NULL) { return 0; } que.push(root); int depth=0; while(!que.empty()) { int size=que.size(); depth++; for(int i=0;i<size;i++) { TreeNode* node=que.front(); que.pop(); if(node->left) { que.push(node->left); } if(node->right) { que.push(node->right); } if(node->left==nullptr && node->right==nullptr) { return depth; } } } return depth; } };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。