742. Closest Leaf in a Binary Tree

xiaoxiao2021-02-28  7

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; *//*题意是寻找离k最近的叶子节点。例如example 3, 6到2的距离是4,5,6三条边,所以是33到2的距离是1,3 两条边,所以是3离2最近的叶子节点。1. 构建反向链接,就是k路线上的节点能找到自己的父节点,用于BFS遍历2. 从K开始,BFS遍历,3个方向。    1. 左子树    2. 右子树    3. 父节点。*/class Solution {public: int findClosestLeaf(TreeNode* root, int k) { unordered_map<TreeNode*, TreeNode*> mpChildToParent; queue<TreeNode*> q; TreeNode* pKNode = findK(root, k, mpChildToParent); q.push(pKNode); unordered_set<TreeNode*> stVisited; stVisited.insert(pKNode); while (!q.empty()) { TreeNode* p = q.front(); q.pop(); if (!p->left && !p->right) return p->val; //if (!p->left && p->right && !stVisited.count(p->right)) if (p->right && !stVisited.count(p->right)) { q.push(p->right); stVisited.insert(p->right); } //if (!p->right && p->left && !stVisited.count(p->left)) if (p->left && !stVisited.count(p->left)) { q.push(p->left); stVisited.insert(p->left); } if (mpChildToParent.count(p) && !stVisited.count(mpChildToParent[p])) { q.push(mpChildToParent[p]); stVisited.insert(mpChildToParent[p]); } } return -1; }private: TreeNode* findK(TreeNode* root, int k, unordered_map<TreeNode*, TreeNode*>& mp) { if (!root) return root; if (root->val == k) return root; TreeNode* left = NULL; TreeNode* right = NULL; if (root->left) { mp[root->left] = root; //return findK(root->left,k,mp); left = findK(root->left, k, mp); } if (root->right) { mp[root->right] = root; //return findK(root->right,k,mp); right = findK(root->right, k, mp); } return left ? left : right ? right : NULL; }};

转载请注明原文地址: https://www.6miu.com/read-2250221.html

最新回复(0)