原文:
给定一个二叉树和两个数字 p 和 k ，任务是在常数空间中从二叉树打印给定数字 p 的kt8】以便后继者。 示例:
输入:树:
1 / \ 12 11 / / \ 3 4 13 \ / 15 9p = 12，k = 4 输出: 1 4 15 11 解释: 有序遍历:3 12 1 4 15 11 9 13 节点 12 的 4 个有序后继节点是{1，4，15，11} 输入:树:
5 / \ 21 77 / \ \ 61 16 36 \ / 10 3 / 23p = 23，k = 3 输出: 10 5 77 解释: 有序遍历:61 21 16 23 10 5 77 3 36 节点 23 的 3 个有序后继节点是{10，5，77}。
方法: 为了解决这个问题，我们使用 来避免使用任何额外的空间。在生成有序序列时搜索节点“p”。找到后，按顺序打印下一个出现的 k 节点。 以下是上述方法的实施:
c
// c implementation to print k inorder
// successor of the binary tree
// without using extra space
#include
using namespace std;
/* a binary tree node has data,
a pointer to left child
and a pointer to right child */
struct tnode {
int data;
struct tnode* left;
struct tnode* right;
};
/* function to traverse the
binary tree without recursion and
without stack */
void morristraversal(struct tnode* root,
int p, int k)
{
struct tnode *current, *pre;
if (root == null)
return;
bool flag = false;
current = root;
while (current != null) {
// check if the left child exists
if (current->left == null) {
if (flag == true) {
cout << current->data
<< " ";
k--;
}
if (current->data == p)
flag = true;
// check if k is 0
if (k == 0)
flag = false;
// move current to its right
current = current->right;
}
else {
// find the inorder predecessor
// of current
pre = current->left;
while (pre->right != null
&& pre->right != current)
pre = pre->right;
/* make current as the right
child of its inorder
predecessor */
if (pre->right == null) {
pre->right = current;
current = current->left;
}
/* revert the changes made in the
'if' part to restore the original
tree i.e., fix the right child
of predecessor */
else {
pre->right = null;
if (flag == true) {
cout << current->data
<< " ";
k--;
}
if (current->data == p)
flag = true;
if (k == 0)
flag = false;
current = current->right;
}
}
}
}
/* function that allocates
a new node with the
given data and null left
and right pointers. */
struct tnode* newtnode(int data)
{
struct tnode* node = new tnode;
node->data = data;
node->left = null;
node->right = null;
return (node);
}
/* driver code*/
int main()
{
struct tnode* root = newtnode(1);
root->left = newtnode(12);
root->right = newtnode(11);
root->left->left = newtnode(3);
root->right->left = newtnode(4);
root->right->right = newtnode(13);
root->right->left->right = newtnode(15);
root->right->right->left = newtnode(9);
int p = 12;
int k = 4;
morristraversal(root, p, k);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java implementation to print k inorder
// successor of the binary tree
// without using extra space
// a binary tree tnode has data,
// a pointer to left child
// and a pointer to right child
class tnode
{
int data;
tnode left, right;
tnode(int item)
{
data = item;
left = right = null;
}
}
class binarytree{
tnode root;
// function to traverse a binary tree
// without recursion and without stack
void morristraversal(tnode root, int p, int k)
{
tnode current, pre;
if (root == null)
return;
boolean flag = false;
current = root;
while (current != null)
{
if (current.left == null)
{
if (flag == true)
{
system.out.print(current.data " ");
k--;
}
if (current.data == p)
{
flag = true;
}
if (k == 0)
{
flag = false;
}
current = current.right;
}
else
{
// find the inorder predecessor
// of current
pre = current.left;
while (pre.right != null &&
pre.right != current)
pre = pre.right;
// make current as right child of
// its inorder predecessor
if (pre.right == null)
{
pre.right = current;
current = current.left;
}
// revert the changes made in the
// 'if' part to restore the original
// tree i.e., fix the right child of
// predecessor
else
{
pre.right = null;
if (flag == true)
{
system.out.print(current.data " ");
k--;
}
if (current.data == p)
{
flag = true;
}
if (k == 0)
{
flag = false;
}
current = current.right;
}
}
}
}
// driver code
public static void main(string args[])
{
binarytree tree = new binarytree();
tree.root = new tnode(1);
tree.root.left = new tnode(12);
tree.root.right = new tnode(11);
tree.root.left.left = new tnode(3);
tree.root.right.left = new tnode(4);
tree.root.right.right = new tnode(13);
tree.root.right.left.right = new tnode(15);
tree.root.right.right.left = new tnode(9);
int p = 12;
int k = 4;
tree.morristraversal(tree.root, p, k);
}
}
// this code is contributed by mohammad mudassir
python 3
# python3 implementation to print k inorder
# successor of the binary tree
# without using extra space
''' a binary tree node has data,
a pointer to left child
and a pointer to right child '''
class tnode:
def __init__(self, data):
self.data = data
self.left = none
self.right = none
''' function to traverse the
binary tree without recursion and
without stack '''
def morristraversal(root, p, k):
current = none
pre = none
if (root == none):
return;
flag = false;
current = root;
while (current != none):
# check if the left child exists
if (current.left == none):
if (flag == true):
print(current.data, end = ' ')
k -= 1
if (current.data == p):
flag = true;
# check if k is 0
if (k == 0):
flag = false;
# move current to its right
current = current.right;
else:
# find the inorder predecessor
# of current
pre = current.left
while (pre.right != none and pre.right != current):
pre = pre.right;
# make current as the right
#child of its inorder predecessor
if(pre.right == none):
pre.right = current;
current = current.left;
# revert the changes made in the
# 'if' part to restore the original
# tree i.e., fix the right child
# of predecessor
else:
pre.right = none;
if (flag == true):
print(current.data, end = ' ')
k -= 1
if (current.data == p):
flag = true;
if (k == 0):
flag = false;
current = current.right;
''' function that allocates
a new node with the
given data and none left
and right pointers. '''
def newtnode(data):
node = tnode(data);
return (node);
# driver code
if __name__=='__main__':
root = newtnode(1);
root.left = newtnode(12);
root.right = newtnode(11);
root.left.left = newtnode(3);
root.right.left = newtnode(4);
root.right.right = newtnode(13);
root.right.left.right = newtnode(15);
root.right.right.left = newtnode(9);
p = 12;
k = 4;
morristraversal(root, p, k);
# this code is contributed by rutvik_56
c
// c# program to print inorder traversal
// without recursion and stack
using system;
// a binary tree tnode has data,
// pointer to left child and a
// pointer to right child
class binarytree{
tnode root;
public class tnode
{
public int data;
public tnode left, right;
public tnode(int item)
{
data = item;
left = right = null;
}
}
// function to traverse binary tree without
// recursion and without stack
void morristraversal(tnode root, int p, int k)
{
tnode current, pre;
if (root == null)
return;
current = root;
bool flag = false;
while (current != null)
{
if (current.left == null)
{
if (flag == true)
{
console.write(current.data " ");
k--;
}
if (current.data == p)
{
flag = true;
}
if (k == 0)
{
flag = false;
}
current = current.right;
}
else
{
// find the inorder predecessor
// of current
pre = current.left;
while (pre.right != null &&
pre.right != current)
pre = pre.right;
// make current as right child
// of its inorder predecessor
if (pre.right == null)
{
pre.right = current;
current = current.left;
}
// revert the changes made in
// if part to restore the original
// tree i.e., fix the right child
// of predecessor
else
{
pre.right = null;
if (flag == true)
{
console.write(current.data " ");
k--;
}
if (current.data == p)
{
flag = true;
}
if (k == 0)
{
flag = false;
}
current = current.right;
}
}
}
}
// driver code
public static void main(string []args)
{
binarytree tree = new binarytree();
tree.root = new tnode(1);
tree.root.left = new tnode(12);
tree.root.right = new tnode(11);
tree.root.left.left = new tnode(3);
tree.root.right.left = new tnode(4);
tree.root.right.right = new tnode(13);
tree.root.right.left.right = new tnode(15);
tree.root.right.right.left = new tnode(9);
int p = 12;
int k = 4;
tree.morristraversal(tree.root, p, k);
}
}
// this code is contributed by mohammad mudassir
java 描述语言
output:
1 4 15 11
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
