网站开发员工作职责,怎样做好企业文化建设,网易企业邮箱登录口入口,企业门户网站需求分析1. 题目
二叉树上有 n 个节点#xff0c;按从 0 到 n-1 编号#xff0c;其中节点 i 的两个子节点分别是 leftChild[i] 和 rightChild[i]。
只有 所有 节点能够形成且 只 形成 一颗 有效的二叉树时#xff0c;返回 true#xff1b;否则返回 false。
如果节点 i 没有左子节…1. 题目
二叉树上有 n 个节点按从 0 到 n-1 编号其中节点 i 的两个子节点分别是 leftChild[i] 和 rightChild[i]。
只有 所有 节点能够形成且 只 形成 一颗 有效的二叉树时返回 true否则返回 false。
如果节点 i 没有左子节点那么 leftChild[i] 就等于 -1。右子节点也符合该规则。
注意节点没有值本问题中仅仅使用节点编号。
示例 1
输入n 4, leftChild [1,-1,3,-1], rightChild [2,-1,-1,-1]
输出true示例 2
输入n 4, leftChild [1,-1,3,-1], rightChild [2,3,-1,-1]
输出false示例 3
输入n 2, leftChild [1,0], rightChild [-1,-1]
输出false示例 4
输入n 6, leftChild [1,-1,-1,4,-1,-1], rightChild [2,-1,-1,5,-1,-1]
输出false提示
1 n 10^4
leftChild.length rightChild.length n
-1 leftChild[i], rightChild[i] n - 1来源力扣LeetCode 链接https://leetcode-cn.com/problems/validate-binary-tree-nodes 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
参考图的数据结构出入度概念二叉树可以看做特殊的图记录每个节点的入度root的入度为0且root只有一个其他节点的入度都只能为1且总的入度等于 n-1
class Solution {
public:bool validateBinaryTreeNodes(int n, vectorint leftChild, vectorint rightChild) {int indegree[n] {0};bool findroot false;int i, sum 0;for(i 0; i n; i){if(leftChild[i] ! -1)indegree[leftChild[i]];if(rightChild[i] ! -1)indegree[rightChild[i]]; }for(i 0; i n; i){if(!findroot indegree[i]0)findroot true;else if(findroot indegree[i]0)return false;else if(indegree[i] 1)return false;sum indegree[i];}if(sum ! n-1)return false;return true;}
};
