863. 二叉树中所有距离为 K 的结点

这篇具有很好参考价值的文章主要介绍了863. 二叉树中所有距离为 K 的结点。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

863. 二叉树中所有距离为 K 的结点

863. 二叉树中所有距离为 K 的结点,LeetCode刷题,深度优先,算法


C代码:dfs文章来源地址https://www.toymoban.com/news/detail-698814.html

/**
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

typedef struct {
    int key;
    struct TreeNode* node;
    UT_hash_handle hh;
} HashTable;

HashTable* head;
int* ans;
int ansSize;

void addToHash(int ikey, struct TreeNode* node) {
    HashTable* out = NULL;
    HASH_FIND_INT(head, &ikey, out); // 去找当前值的父节点
    if (out == NULL) {
        out = (HashTable*)malloc(sizeof(HashTable));
        out->key = ikey;
        out->node = node;  // 保存当前节点的父节点
        HASH_ADD_INT(head, key, out);
    } else {
        out->node = node;
    }
}

void findParents(struct TreeNode* root) {
    if (root->left != NULL) {
        addToHash(root->left->val, root);
        findParents(root->left);
    }
    if (root->right != NULL) {
        addToHash(root->right->val, root);
        findParents(root->right);
    }
}

struct TreeNode* query(int ikey) {
    HashTable* out = NULL;
    HASH_FIND_INT(head, &ikey, out);
    if (out == NULL) {
        return NULL;
    }
    return out->node;
}

// 从target节点往3个方向搜索,确保3个方向的途经点不能再dfs回去!
void findAns(struct TreeNode* node, struct TreeNode* from, int depth, int k) {
    if (node == NULL) {
        return;
    }
    if (depth == k) {  // 前序处理
        ans[ansSize++] = node->val;
        return;
    }
    if (node->left != from) {  // 搜索左右子节点,from是途径过的上一个结点
        findAns(node->left, node, depth + 1, k);
    }
    if (node->right != from) {
        findAns(node->right, node, depth + 1, k);
    }
    if (query(node->val) != from) {  // 顺着父节点往上搜索,node的父节点不等于from
        findAns(query(node->val), node, depth + 1, k);
    }
}

int* distanceK(struct TreeNode* root, struct TreeNode* target, int k, int* returnSize) {
    head = NULL;                      // target是个结点
    ans = (int*)malloc(sizeof(int) * 500);
    ansSize = 0;

    findParents(root);  // 从root出发 DFS,记录每个结点的父结点

    findAns(target, NULL, 0, k); // 从target出发 DFS,寻找所有深度为 k 的结点
    
    *returnSize = ansSize;
    return ans;
}

到了这里,关于863. 二叉树中所有距离为 K 的结点的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 设计一个求结点x在二叉树中的双亲结点算法

    要设计一个求二叉树中指定节点 x 的双亲节点的算法,可以按照以下步骤进行: 创建一个递归函数  findParent(root, x) ,其中  root  是当前子树的根节点, x  是要查找其双亲节点的节点。 首先检查根节点是否为空或者根节点是否就是要查找的节点 x,若是,则说明 x 没有双亲

    2024年02月04日
    浏览(42)
  • 假设二叉树中每个结点值为单个字符,采用二叉链存储结构存储。设计一个算法,求二叉树b中第k层上叶子结点个数(非递归算法)。

    int LevelCount(BiTNode *b,int k){         BiTNode *p=b,*temp[Maxsize];         int layer=0,count=0, m=0, n=1; (m: 上一层结点的尾   n: 当层结点的尾 )         temp[0]=NULL;         temp[1]=p;         if(p==NULL) return 0;// 二叉树为空,任意层结点个数均为 0         while(1){          

    2024年02月04日
    浏览(49)
  • 求二叉树中,任意两个节点之间的距离最大值是多少

    提示:本节仍然是重点说二叉树的DP递归套路,非常重要而且容易理解 二叉树的动态规划树形DP递归套路系列文章有这些,可以帮助你快速掌握树形DP的题目解题思想,就一个套路: (1)判断二叉树是否为平衡二叉树?树形DP,树形动态规划的递归套路 请你求一颗二叉树中,

    2023年04月11日
    浏览(48)
  • 算法刷题Day 20 最大二叉树+合并二叉树+二叉搜索树中的搜索+验证二叉搜索树

    递归 递归 迭代 递归 迭代 遇到两个坑的地方: 递归的时候,不能光验证左子树的根节点小于当前根节点,右子树的根节点大于但当前根节点,别忘了左子树上的每一个节点都要求比根节点要小,右子树上的每一个节点都要求比根节点大。 根节点跟左(右)子树中的某一个节

    2024年02月16日
    浏览(43)
  • LeetCode算法递归类—二叉树中的最大路径和

    目录 124. 二叉树中的最大路径和 - 力扣(LeetCode) 题解: 代码: 运行结果: 二叉树中的  路径  被定义为一条节点序列,序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中  至多出现一次  。该路径  至少包含一个  节点,且不一定经过根节点。 路径和

    2024年02月12日
    浏览(38)
  • leetcode: 1261: 在受污染的二叉树中查找元素

    给出一个满足下述规则的二叉树: root.val == 0 如果  treeNode.val == x  且  treeNode.left != null ,那么  treeNode.left.val == 2 * x + 1 如果  treeNode.val == x  且  treeNode.right != null ,那么  treeNode.right.val == 2 * x + 2 现在这个二叉树受到「污染」,所有的  treeNode.val  都变成了  -1 。 请你先

    2024年03月12日
    浏览(33)
  • leetcode做题笔记124. 二叉树中的最大路径和

    二叉树中的  路径  被定义为一条节点序列,序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中  至多出现一次  。该路径  至少包含一个  节点,且不一定经过根节点。 路径和  是路径中各节点值的总和。 给你一个二叉树的根节点  root  ,返回其  最

    2024年02月10日
    浏览(47)
  • 算法刷题Day 21 二叉搜索树的最小绝对差+二叉搜索树中的众数+二叉树的最近公共祖先

    递归 递归中保存前一个节点的指针的方法,需要再学习,巩固一下 迭代 一下子就想到的方法:遍历一遍二叉搜索树,把各个节点的值存进哈希表里(节点值——键,出现频率——值),再遍历哈希表找众数 一般方法 既然是二叉搜索树,中序遍历就是有序的。有序的话,我

    2024年02月16日
    浏览(43)
  • 算法训练day20Leetcode654最大二叉树617合并二叉树700二叉树中的1搜索98验证二叉搜索树

    https://leetcode.cn/problems/maximum-binary-tree/description/ 中序遍历递归,找到最大值然后作为根节点 凡是构造二叉树的题目都用前序遍历 (中左右) 为先构造中间节点,然后递归构造左子树和右子树。 确定递归函数的参数和返回值 参数传入的是存放元素的数组,返回该数组构造的二

    2024年01月21日
    浏览(41)
  • Leetcode每日一题:1448. 统计二叉树中好节点的数目

    给你一棵根为  root  的二叉树,请你返回二叉树中好节点的数目。 「好节点」X 定义为:从根到该节点 X 所经过的节点中,没有任何节点的值大于 X 的值。 示例 1: 示例 2: 示例 3: 提示: 二叉树中节点数目范围是  [1, 10^5]  。 每个节点权值的范围是  [-10^4, 10^4]  。 显然

    2024年02月11日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包