二叉树问题（二）-LeetCode 965、563、993、958、919（树深度，层次遍历）
- 2019 年 12 月 24 日
- 筆記
作者：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
