文章
7
粉丝
0
获赞
0
访问
466
1. 使用递归方法,从叶子节点开始逐步向上判断,如果左右子树有一个不存在,那么这个节点一定不符合要求,如果左右子树节点都存在,那么我需要维护左右子树权值的范围(在节点中存储),例如上图:根节点4的左子树范围为[1, 3], 右子树范围为 [6,6]
接下来我们分别求左右子树的最小距离: 假设当前节点权值为 val, 左子树的范围为 [a, b], 那么左子树的最小距离为 min{abs(val - a), abs(val - b)}, 其中 abs 为绝对值函数。 右子树最小距离同理, 之后判断两个距离是否相等即可
2.
struct TreeNode {
int leftVal, rightVal; // 用来记录以这个节点为根节点的子树的最大值和最小值
};
void findNodes(TreeNode* node, int* ans) {
if(node->left != null)
findNode(node->left, ans);
if(node->right != null)
findNode(node->right, ans);
// 接下来是计算当前节点为根节点的子树的最大值和最小值
node->leftVal = node->rightVal = node->val;
if(node->left != null) {
node->leftVal = min(node->left->leftVal, node->leftVal);
node->rightVal = max(node->left->rightVal, node->rightVal);
}
if(node->right != null) {
node->leftVal = min(node->right->leftVal, node->leftVal);
node->rightVal = max(nod...
登录后发布评论
暂无评论,来抢沙发