二叉树问题（二）-LeetCode 965、563、993、958、919（树深度，层次遍历）
二叉树问题（二）-LeetCode 965、563、993、958、919（树深度，层次遍历）
作者：TeddyZhang，公众号：算法工程师之路
二叉树问题（二）：
LeetCode # 965 563 993 958 919
1
编程题
【LeetCode #965】单值二叉树
如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。 只有给定的树是单值二叉树时，才返回 true；否则返回 false。
(迭代法，中序遍历)
class Solution {
public:
bool isUnivalTree(TreeNode* root) {
stack<TreeNode*> sta;
TreeNode* pre = nullptr;
TreeNode* cur = root;
while(cur != nullptr || !sta.empty()) {
if(cur != nullptr) {
sta.push(cur);
cur = cur->left;
}else {
cur = sta.top();
sta.pop();
if (pre && pre->val != cur->val) {
return false;
}
pre = cur;
cur = cur->right;
}
}
return true;
}
};
(递归法)
class Solution {
public:
bool isUnivalTree(TreeNode* root) {
if (root == nullptr) return true;
if (root->left && root->left->val != root->val) {
return false;
}
if (root->right && root->right->val != root->val) {
return false;
}
return isUnivalTree(root->left) && isUnivalTree(root->right);
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/univalued-binary-tree/
【LeetCode #563】二叉树的坡度
给定一个二叉树，计算整个树的坡度。
一个树的节点的坡度定义即为，该节点左子树的结点之和和右子树结点之和的差的绝对值。空结点的的坡度是0。 整个树的坡度就是其所有节点的坡度之和。
示例: 输入: 1 / \ 2 3 输出: 1 解释: 结点的坡度 2 : 0 结点的坡度 3 : 0 结点的坡度 1 : |2-3| = 1 树的坡度 : 0 + 0 + 1 = 1
解题思路：
首先我们写出一个计算一个二叉树中子树的节点和的递归式子，然后再递归参数中使用count来累加两个子树节点和的差值，最后返回count即可。注意使用引用传递而不是值传递。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int add(TreeNode* node, int& count) {
if(node == nullptr) return ;
int left = add(node->left, count);
int right = add(node->right, count);
count += abs(left - right);
return left+right+node->val;
}
int findTilt(TreeNode* root) {
int res = ;
add(root, res);
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/binary-tree-tilt
【LeetCode #993】二叉树的堂兄节点
在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。 如果二叉树的两个节点深度相同，但父节点不同，则它们是一对堂兄弟节点。 我们给出了具有唯一值的二叉树的根节点 root，以及树中两个不同节点的值 x 和 y。 只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true。否则，返回 false
解题思路：
使用pair类型储存对应x节点以及y节点的深度和父节点的值，然后进行比较即可。 注意该二叉树中的值都是唯一的，没有重复的。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void find(TreeNode* node, int val, int dep, int par, pair<int, int>& res) {
if (node == nullptr) return;
if (node->val == val) {
res.first = dep;
res.second = par;
return;
} else {
find(node->left, val, dep+, node->val, res);
find(node->right, val, dep+, node->val, res);
}
}
bool isCousins(TreeNode* root, int x, int y) {
pair<int, int> res1, res2;
find(root, x, , -1, res1); // 根节点的父节点值设为-1
find(root, y, , -1, res2);
return (res1.first == res2.first) && (res1.second != res2.second);
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/cousins-in-binary-tree
【LeetCode #958】二叉树的完全性检验（完全二叉树）
给定一个二叉树，确定它是否是一个完全二叉树。 百度百科中对完全二叉树的定义如下： 若设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。（注：第 h 层可能包含 1~ 2h 个节点。）
解题思路：
使用类似层次遍历的方法，使用flag标记遇到了nullptr，然后置为true，接着判断当flag=true时，接下来访问的节点是否为空，如果都为空，则说明是完全二叉树，否则不是。 注意：为了将stack中加入nullptr，因此只判断tmp是否为空即可！
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isCompleteTree(TreeNode* root) {
bool flag = false;
queue<TreeNode*> que;
que.push(root);
while(!que.empty()) {
TreeNode* tmp = que.front();
que.pop();
if (tmp == nullptr) flag = true;
if (flag && tmp) return false; // 遇到nullptr，后面都应该是nullptr
if (tmp) { // 与层次遍历不同，只需要判断tmp是否为nullptr
que.push(tmp->left);
que.push(tmp->right);
}
}
return true;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/check-completeness-of-a-binary-tree
【LeetCode #919】完全二叉树插入器
完全二叉树是每一层（除最后一层外）都是完全填充（即，结点数达到最大）的，并且所有的结点都尽可能地集中在左侧。 设计一个用完全二叉树初始化的数据结构 CBTInserter，它支持以下几种操作：
CBTInserter(TreeNode root) 使用头结点为 root 的给定树初始化该数据结构； CBTInserter.insert(int v) 将 TreeNode 插入到存在值为 node.val = v 的树中以使其保持完全二叉树的状态，并返回插入的 TreeNode 的父结点的值； CBTInserter.get_root() 将返回树的头结点。
解题思路：
LeetCode上的翻译很烂，简单来说，就是现在有一颗root为根节点的完全二叉树，当我们向二叉树中插入节点的，也应该保证完全二叉树的性质，这在里面使用层次遍历的方法，寻找某个节点的左节点或者右节点为nullptr的节点，定为待插入节点root_. 注意如果向某个节点的右节点插入了一个节点，那么待插入节点root_会发生变化！
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class CBTInserter {
public:
queue<TreeNode*> que;
// 注意root为一个完全二叉树
CBTInserter(TreeNode* root) : root_(root), node_(nullptr) {
que.push(root_);
while(!que.empty()) {
TreeNode* tmp = que.front();
que.pop();
if (tmp->left) que.push(tmp->left);
if (tmp->right) que.push(tmp->right);
if (node_ == nullptr && (tmp->left == nullptr || tmp->right == nullptr)) {
node_ = tmp;
break;
}
}
}
int insert(int v) {
TreeNode* newNode = new TreeNode(v);
int father = node_->val;
if(node_->left == nullptr) node_->left = newNode;
else {
node_->right = newNode;
if (!que.empty()) {
node_ = que.front();
que.pop();
}
}
return father;
}
TreeNode* get_root() {
return root_;
}
private:
TreeNode* node_; // 用来储存待插入节点的位置
TreeNode* root_; // 用来储存树根节点的位置
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/complete-binary-tree-inserter
腾讯云开发者
