找到给定键的下一个右节点|设置 2
原文:https://www . geesforgeks . org/find-next-right-node-given-key-set-2/
给定一棵二叉树和二叉树中的一个键，找到给定键右边的节点。如果右侧没有节点，则返回空值。预期时间复杂度为 O(n)，其中 n 是给定二叉树中的节点数。 例如，考虑下面的二叉树。2 的输出是 6，4 的输出是 5。10、6 和 5 的输出为空。
10
/ \
2 6
/ \ \
8 4 5
Input : 2
Output : 6
Input : 4
Output : 5
在我们之前的帖子中，我们讨论了一个使用级序遍历的解决方案。在这篇文章中，我们将讨论一个基于 Preorder 遍历的解决方案，它需要恒定的辅助空间。 想法是使用前序遍历遍历给定的树，并搜索给定的键。找到给定的密钥后，我们将标记该密钥的级别号。现在，我们将在同一级别找到的下一个节点是位于给定键右侧的所需节点。 以下是上述思路的实现:
C++
/* C++ program to find next right of a given key
using preorder traversal */
#include <bits/stdc++.h>
using namespace std;
// A Binary Tree Node
struct Node {
struct Node *left, *right;
int key;
};
// Utility function to create a new tree node
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return temp;
}
// Function to find next node for given node
// in same level in a binary tree by using
// pre-order traversal
Node* nextRightNode(Node* root, int k, int level,
int& value_level)
{
// return null if tree is empty
if (root == NULL)
return NULL;
// if desired node is found, set value_level
// to current level
if (root->key == k) {
value_level = level;
return NULL;
}
// if value_level is already set, then current
// node is the next right node
else if (value_level) {
if (level == value_level)
return root;
}
// recurse for left subtree by increasing level by 1
Node* leftNode = nextRightNode(root->left, k,
level + 1, value_level);
// if node is found in left subtree, return it
if (leftNode)
return leftNode;
// recurse for right subtree by increasing level by 1
return nextRightNode(root->right, k, level + 1,
value_level);
}
// Function to find next node of given node in the
// same level in given binary tree
Node* nextRightNodeUtil(Node* root, int k)
{
int value_level = 0;
return nextRightNode(root, k, 1, value_level);
}
// A utility function to test above functions
void test(Node* root, int k)
{
Node* nr = nextRightNodeUtil(root, k);
if (nr != NULL)
cout << "Next Right of " << k << " is "
<< nr->key << endl;
else
cout << "No next right node found for "
<< k << endl;
}
// Driver program to test above functions
int main()
{
// Let us create binary tree given in the
// above example
Node* root = newNode(10);
root->left = newNode(2);
root->right = newNode(6);
root->right->right = newNode(5);
root->left->left = newNode(8);
root->left->right = newNode(4);
test(root, 10);
test(root, 2);
test(root, 6);
test(root, 5);
test(root, 8);
test(root, 4);
return 0;
}
Java 语言(一种计算机语言，尤用于创建网站)
/* Java program to find next right of a given key
using preorder traversal */
import java.util.*;
class GfG {
// A Binary Tree Node
static class Node {
Node left, right;
int key;
}
// Utility function to create a new tree node
static Node newNode(int key)
{
Node temp = new Node();
temp.key = key;
temp.left = null;
temp.right = null;
return temp;
}
// Function to find next node for given node
// in same level in a binary tree by using
// pre-order traversal
static Node nextRightNode(Node root, int k, int level, int[] value)
{
// return null if tree is empty
if (root == null)
return null;
// if desired node is found, set value[0]
// to current level
if (root.key == k) {
value[0] = level;
return null;
}
// if value[0] is already set, then current
// node is the next right node
else if (value[0] != 0) {
if (level == value[0])
return root;
}
// recurse for left subtree by increasing level by 1
Node leftNode = nextRightNode(root.left, k, level + 1, value);
// if node is found in left subtree, return it
if (leftNode != null)
return leftNode;
// recurse for right subtree by increasing level by 1
return nextRightNode(root.right, k, level + 1, value);
}
// Function to find next node of given node in the
// same level in given binary tree
static Node nextRightNodeUtil(Node root, int k)
{
int[] v = new int[1];
v[0] = 0;
return nextRightNode(root, k, 1, v);
}
// A utility function to test above functions
static void test(Node root, int k)
{
Node nr = nextRightNodeUtil(root, k);
if (nr != null)
System.out.println("Next Right of " + k + " is "+ nr.key);
else
System.out.println("No next right node found for " + k);
}
// Driver program to test above functions
public static void main(String[] args)
{
// Let us create binary tree given in the
// above example
Node root = newNode(10);
root.left = newNode(2);
root.right = newNode(6);
root.right.right = newNode(5);
root.left.left = newNode(8);
root.left.right = newNode(4);
test(root, 10);
test(root, 2);
test(root, 6);
test(root, 5);
test(root, 8);
test(root, 4);
}
}
// This code has been contributed by Mukul Sharma
Python 3
# Python3 program to find next right of a
# given key using preorder traversal
# class to create a new tree node
class newNode:
def __init__(self, key):
self.key = key
self.left = self.right = None
# Function to find next node for given node
# in same level in a binary tree by using
# pre-order traversal
def nextRightNode(root, k, level, value_level):
# return None if tree is empty
if (root == None):
return None
# if desired node is found, set
# value_level to current level
if (root.key == k):
value_level[0] = level
return None
# if value_level is already set, then
# current node is the next right node
elif (value_level[0]):
if (level == value_level[0]):
return root
# recurse for left subtree by increasing
# level by 1
leftNode = nextRightNode(root.left, k,
level + 1, value_level)
# if node is found in left subtree,
# return it
if (leftNode):
return leftNode
# recurse for right subtree by
# increasing level by 1
return nextRightNode(root.right, k,
level + 1, value_level)
# Function to find next node of given node
# in the same level in given binary tree
def nextRightNodeUtil(root, k):
value_level = [0]
return nextRightNode(root, k, 1, value_level)
# A utility function to test above functions
def test(root, k):
nr = nextRightNodeUtil(root, k)
if (nr != None):
print("Next Right of", k, "is", nr.key)
else:
print("No next right node found for", k)
# Driver Code
if __name__ == '__main__':
# Let us create binary tree given in the
# above example
root = newNode(10)
root.left = newNode(2)
root.right = newNode(6)
root.right.right = newNode(5)
root.left.left = newNode(8)
root.left.right = newNode(4)
test(root, 10)
test(root, 2)
test(root, 6)
test(root, 5)
test(root, 8)
test(root, 4)
# This code is contributed by PranchalK
C
/* C# program to find next right of a given key
using preorder traversal */
using System;
class GfG
{
public class V
{
public int value_level = 0;
}
// A Binary Tree Node
public class Node
{
public Node left, right;
public int key;
}
// Utility function to create a new tree node
static Node newNode(int key)
{
Node temp = new Node();
temp.key = key;
temp.left = null;
temp.right = null;
return temp;
}
// Function to find next node for given node
// in same level in a binary tree by using
// pre-order traversal
static Node nextRightNode(Node root, int k,
int level, V value)
{
// return null if tree is empty
if (root == null)
return null;
// if desired node is found, set
// value_level to current level
if (root.key == k)
{
value.value_level = level;
return null;
}
// if value_level is already set, then current
// node is the next right node
else if (value.value_level != 0)
{
if (level == value.value_level)
return root;
}
// recurse for left subtree by increasing level by 1
Node leftNode = nextRightNode(root.left,
k, level + 1, value);
// if node is found in left subtree, return it
if (leftNode != null)
return leftNode;
// recurse for right subtree by
// increasing level by 1
return nextRightNode(root.right, k,
level + 1, value);
}
// Function to find next node of given node in the
// same level in given binary tree
static Node nextRightNodeUtil(Node root, int k)
{
V v = new V();
return nextRightNode(root, k, 1, v);
}
// A utility function to test above functions
static void test(Node root, int k)
{
Node nr = nextRightNodeUtil(root, k);
if (nr != null)
Console.WriteLine("Next Right of " +
k + " is "+ nr.key);
else
Console.WriteLine("No next right node" +
" found for " + k);
}
// Driver main
public static void Main(String[] args)
{
// Let us create binary tree given in the
// above example
Node root = newNode(10);
root.left = newNode(2);
root.right = newNode(6);
root.right.right = newNode(5);
root.left.left = newNode(8);
root.left.right = newNode(4);
test(root, 10);
test(root, 2);
test(root, 6);
test(root, 5);
test(root, 8);
test(root, 4);
}
}
// This code contributed by Rajput-Ji
java 描述语言
<script>
/* Javascript program to find next right of a given key
using preorder traversal */
// A Binary Tree Node
class Node
{
constructor(key) {
this.left = null;
this.right = null;
this.key = key;
}
}
// Utility function to create a new tree node
function newNode(key)
{
let temp = new Node(key);
return temp;
}
// Function to find next node for given node
// in same level in a binary tree by using
// pre-order traversal
function nextRightNode(root, k, level, value)
{
// return null if tree is empty
if (root == null)
return null;
// if desired node is found, set value[0]
// to current level
if (root.key == k) {
value[0] = level;
return null;
}
// if value[0] is already set, then current
// node is the next right node
else if (value[0] != 0) {
if (level == value[0])
return root;
}
// recurse for left subtree by increasing level by 1
let leftNode = nextRightNode(root.left, k, level + 1, value);
// if node is found in left subtree, return it
if (leftNode != null)
return leftNode;
// recurse for right subtree by increasing level by 1
return nextRightNode(root.right, k, level + 1, value);
}
// Function to find next node of given node in the
// same level in given binary tree
function nextRightNodeUtil(root, k)
{
let v = new Array(1);
v[0] = 0;
return nextRightNode(root, k, 1, v);
}
// A utility function to test above functions
function test(root, k)
{
let nr = nextRightNodeUtil(root, k);
if (nr != null)
document.write("Next Right of " + k + " is "+ nr.key +
"</br>");
else
document.write("No next right node found for " + k +
"</br>");
}
// Let us create binary tree given in the
// above example
let root = newNode(10);
root.left = newNode(2);
root.right = newNode(6);
root.right.right = newNode(5);
root.left.left = newNode(8);
root.left.right = newNode(4);
test(root, 10);
test(root, 2);
test(root, 6);
test(root, 5);
test(root, 8);
test(root, 4);
</script>
输出:
No next right node found for 10
Next Right of 2 is 6
No next right node found for 6
No next right node found for 5
Next Right of 8 is 4
Next Right of 4 is 5
时间复杂度:O(n) T3】辅助空间: O(1)
版权属于：月萌API www.moonapi.com，转载请注明出处
