3701 · Find Nearest Right Node in Binary TreePRE
Algorithms
This topic is a pre-release topic. If you encounter any problems, please contact us via “Problem Correction”, and we will upgrade your account to VIP as a thank you.
Description
Given a binary tree with a root node root and a node u in the tree, return the node value val of the right-hand node nearest to it in the layer in which the node u is located, or -1 if the node u is the rightmost node in the current layer.
The total number of nodes is between
All nodes in the tree have node values that are unique
u is a node in a binary tree rooted at root
Example
Example 1:
Input:
root = {1,2,3,#,4,5,6}
u = 2
Output:
3
Explanation:
As shown in the figure, in the layer where node 2 is located, the nearest right node is node 3
3701_1.png
Example 2:
Input:
root = {3,1,#,#,2}
u = 1
Output:
-1
Explanation:
As shown in the figure, the layer where node 1 is located has only one node and the nearest right node is not found
解法1：遍历
采用前序遍历。当找到目标节点后，记住当前层次。那么，前序遍历再次到达该层次的时候，访问到的节点就是所求节点。
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param root: The root of the binary tree
* @param u: A node in root
* @return: Node value of the right node
*/
int findNearestRightNode(TreeNode *root, TreeNode *u) {
helper(root, 0, u);
if (findNode) return findNode->val;
return -1;
}
private:
bool find = false;
int targetDepth = -1;
TreeNode *findNode = NULL;
void helper(TreeNode *root, int depth, TreeNode *u) {
if (!root) return;
if (findNode) return;
if (find && depth == targetDepth) {
findNode = root;
return;
}
if (root == u) {
find = true;
targetDepth = depth;
}
helper(root->left, depth + 1, u);
helper(root->right, depth + 1, u);
}
};
写成这样也可以。这样就不用find变量了。
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param root: The root of the binary tree
* @param u: A node in root
* @return: Node value of the right node
*/
int findNearestRightNode(TreeNode *root, TreeNode *u) {
helper(root, 0, u);
if (findNode) return findNode->val;
return -1;
}
private:
int targetDepth = -1;
TreeNode *findNode = NULL;
void helper(TreeNode *root, int depth, TreeNode *u) {
if (!root || findNode) return;
if (root == u) {
targetDepth = depth;
} else if (targetDepth == depth) {
findNode = root;
return;
}
helper(root->left, depth + 1, u);
helper(root->right, depth + 1, u);
}
};
注意: 下面这个写法不对。
只用find是不够的，因为还有些其它同层次的节点在处理，结果会覆盖resValue。
比如说输入：root = [1,2,3,null,4,5,6], u = 4
下面会输出：6。但结果应该是5。
class Solution {
public:
/**
* @param root: The root of the binary tree
* @param u: A node in root
* @return: Node value of the right node
*/
int findNearestRightNode(TreeNode *root, TreeNode *u) {
helper(root, 0, u);
return resValue;
}
private:
bool find = false;
int resValue = -1, targetDepth = -1;
void helper(TreeNode *root, int depth, TreeNode *u) {
if (!root) return;
if (find && depth == targetDepth) {
resValue = root->val;
return;
}
if (root == u) {
find = true;
targetDepth = depth;
}
helper(root->left, depth + 1, u);
helper(root->right, depth + 1, u);
}
};
解法2: bfs
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param root: The root of the binary tree
* @param u: A node in root
* @return: Node value of the right node
*/
int findNearestRightNode(TreeNode *root, TreeNode *u) {
if (!root ||! u) return -1;
queue<TreeNode *> q;
int res = -1;
bool find = false;
q.push(root);
while(!q.empty()) {
int qSize = q.size();
find = false;
for (int i = 0; i < qSize; i++) {
TreeNode *frontNode = q.front();
q.pop();
if (find) return frontNode->val;
if (frontNode == u) find = true;
if (frontNode->left) q.push(frontNode->left);
if (frontNode->right) q.push(frontNode->right);
}
}
return -1;
}
};
