1602

1602. Find Nearest Right Node in Binary Tree (Medium)

Given the root of a binary tree and a node u in the tree, return the nearest node on the same level that is to the right of u, or return null if u is the rightmost node in its level.

 

Example 1:

Input: root = [1,2,3,null,4,5,6], u = 4
Output: 5
Explanation: The nearest node on the same level to the right of node 4 is node 5.

Example 2:

Input: root = [3,null,4,2], u = 2
Output: null
Explanation: There are no nodes to the right of 2.

 

Constraints:

• The number of nodes in the tree is in the range [1, 105].
• 1 <= Node.val <= 105
• All values in the tree are distinct.
• u is a node in the binary tree rooted at root.

Companies:
Google

Related Topics:
Tree, Breadth-First Search, Binary Tree

Solution 1. BFS

// OJ: https://leetcode.com/problems/find-nearest-right-node-in-binary-tree/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    TreeNode* findNearestRightNode(TreeNode* root, TreeNode* u) {
        queue<TreeNode*> q{{root}};
        while (q.size()) {
            int cnt = q.size();
            while (cnt--) {
                auto n = q.front();
                q.pop();
                if (n == u) return cnt ? q.front() : nullptr;
                if (n->left) q.push(n->left);
                if (n->right) q.push(n->right);
            }
        }
        return nullptr;
    }
};

Solution 2. DFS

// OJ: https://leetcode.com/problems/find-nearest-right-node-in-binary-tree/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(H)
class Solution {
public:
    TreeNode* findNearestRightNode(TreeNode* root, TreeNode* u) {
        int depth = -1;
        TreeNode *ans = nullptr;
        function<bool(TreeNode*, int)> dfs = [&](TreeNode *node, int d) {
            if (!node) return false;
            if (node == u) {
                depth = d;
                return false;
            } else if (d == depth) {
                ans = node;
                return true;
            }
            return dfs(node->left, d + 1) || dfs(node->right, d + 1);
        };
        dfs(root, 0);
        return ans;
    }
};