原文:
给定由不同节点和一对节点组成的二叉树。任务是找到并打印二叉树中两个给定节点之间的路径。 例:
输入: n1 = 7，n2 = 4
输出: 7 3 1 4
方法:在文章中已经讨论了解决这个问题的方法。在本文中，将讨论一种甚至优化的递归方法。 在这种递归方法中，以下是步骤:
- 递归地查找第一个值，一旦找到就将该值添加到堆栈中。
- 现在，无论是在回溯还是前向跟踪中，每个被访问的节点都会将值添加到堆栈中，但如果该节点是在前向跟踪中添加的，则在回溯中将其移除，并继续执行此操作，直到找到第二个值或所有节点都被访问。
例如:考虑 7 和 9 之间的路径要在上面的树中找到。我们以 dfs 的形式遍历树，一旦找到值 7，就将其添加到堆栈中。穿越路径 0 - > 1 - > 3 - > 7。 现在回溯时，在堆栈中添加 3 和 1。所以到目前为止，堆栈有[7，3，1]，子级 1 有一个右子级，所以我们首先将它添加到堆栈中。现在，堆栈包含[7，3，1，4]。访问 4 的左子代，将其添加到堆栈中。堆栈现在包含[7，3，1，4，8]。由于没有进一步的节点，我们将返回到前一个节点，并且因为 8 已经被添加到堆栈中，所以删除它。现在节点 4 有了一个正确的子节点，我们将其添加到堆栈中，因为这是我们要寻找的第二个值，不会再有任何递归调用。最后，堆栈包含[7，3，1，4，9]。 以下是上述办法的实施:
c
// cpp implementation of the approach
#include
using namespace std;
// a binary tree node
class node {
public:
int value;
node *left, *right;
node(int value) {
this->value = value;
left = null;
right = null;
}
};
bool firstvaluefound = false;
bool secondvaluefound = false;
stack stk;
node *root = null;
// function to find the path between
// two nodes in binary tree
void pathbetweennode(node *root, int v1, int v2) {
// base condition
if (root == null) return;
// if both the values are found then return
if (firstvaluefound && secondvaluefound) return;
// starting the stack frame with
// isaddedtostack = false flag
bool isaddedtostack = false;
// if one of the value is found then add the
// value to the stack and make the isaddedtostack = true
if (firstvaluefound ^ secondvaluefound) {
stk.push(root);
isaddedtostack = true;
}
// if none of the two values is found
if (!(firstvaluefound && secondvaluefound)) {
pathbetweennode(root->left, v1, v2);
}
// ccopy of current state of firstvaluefound
// and secondvaluefound flag
bool localfirstvaluefound = firstvaluefound;
bool localsecondvaluefound = secondvaluefound;
// if the first value is found
if (root->value == v1) firstvaluefound = true;
// if the second value is found
if (root->value == v2) secondvaluefound = true;
bool localadded = false;
// if one of the value is found and the value
// was not added to the stack yet or there was
// only one value found and now both the values
// are found and was not added to
// the stack then add it
if (((firstvaluefound ^ secondvaluefound) ||
((localfirstvaluefound ^ localsecondvaluefound) &&
(firstvaluefound && secondvaluefound))) &&
!isaddedtostack) {
localadded = true;
stk.push(root);
}
// if none of the two values is found yet
if (!(firstvaluefound && secondvaluefound)) {
pathbetweennode(root->right, v1, v2);
}
if ((firstvaluefound ^ secondvaluefound) && !isaddedtostack && !localadded)
stk.push(root);
if ((firstvaluefound ^ secondvaluefound) && isaddedtostack) stk.pop();
}
// function to find the path between
// two nodes in binary tree
stack pathbetweennode(int v1, int v2)
{
// global root
pathbetweennode(::root, v1, v2);
// if both the values are found
// then return the stack
if (firstvaluefound && secondvaluefound)
{
// global stack object
return ::stk;
}
// if none of the two values is
// found then return empty stack
stack stk;
return stk;
}
// recursive function to print the
// contents of a stack in reverse
void print(stack stk)
{
// if the stack is empty
if (stk.empty()) return;
// get the top value
int value = stk.top()->value;
stk.pop();
// recursive call
print(stk);
// print the popped value
cout << value << " ";
}
// driver code
int main(int argc, char const *argv[])
{
root = new node(0);
root->left = new node(1);
root->right = new node(2);
root->left->left = new node(3);
root->left->right = new node(4);
root->right->left = new node(5);
root->right->right = new node(6);
root->left->left->left = new node(7);
root->left->right->left = new node(8);
root->left->right->right = new node(9);
// find and print the path
stack stck = pathbetweennode(7, 4);
print(stck);
}
// this code is contributed by sanjeev2552
java 语言(一种计算机语言，尤用于创建网站)
// java implementation of the approach
import java.util.stack;
public class gfg {
// a binary tree node
private static class node {
public node left;
public int value;
public node right;
public node(int value)
{
this.value = value;
left = null;
right = null;
}
}
private boolean firstvaluefound = false;
private boolean secondvaluefound = false;
private stack stack = new stack();
private node root = null;
public gfg(node root)
{
this.root = root;
}
// function to find the path between
// two nodes in binary tree
public stack pathbetweennode(int v1, int v2)
{
pathbetweennode(this.root, v1, v2);
// if both the values are found
// then return the stack
if (firstvaluefound && secondvaluefound) {
return stack;
}
// if none of the two values is
// found then return empty stack
return new stack();
}
// function to find the path between
// two nodes in binary tree
private void pathbetweennode(node root, int v1, int v2)
{
// base condition
if (root == null)
return;
// if both the values are found then return
if (firstvaluefound && secondvaluefound)
return;
// starting the stack frame with
// isaddedtostack = false flag
boolean isaddedtostack = false;
// if one of the value is found then add the
// value to the stack and make the isaddedtostack = true
if (firstvaluefound ^ secondvaluefound) {
stack.add(root);
isaddedtostack = true;
}
// if none of the two values is found
if (!(firstvaluefound && secondvaluefound)) {
pathbetweennode(root.left, v1, v2);
}
// ccopy of current state of firstvaluefound
// and secondvaluefound flag
boolean localfirstvaluefound = firstvaluefound;
boolean localsecondvaluefound = secondvaluefound;
// if the first value is found
if (root.value == v1)
firstvaluefound = true;
// if the second value is found
if (root.value == v2)
secondvaluefound = true;
boolean localadded = false;
// if one of the value is found and the value
// was not added to the stack yet or there was
// only one value found and now both the values
// are found and was not added to
// the stack then add it
if (((firstvaluefound ^ secondvaluefound)
|| ((localfirstvaluefound ^ localsecondvaluefound)
&& (firstvaluefound && secondvaluefound)))
&& !isaddedtostack) {
localadded = true;
stack.add(root);
}
// if none of the two values is found yet
if (!(firstvaluefound && secondvaluefound)) {
pathbetweennode(root.right, v1, v2);
}
if ((firstvaluefound ^ secondvaluefound)
&& !isaddedtostack && !localadded)
stack.add(root);
if ((firstvaluefound ^ secondvaluefound)
&& isaddedtostack)
stack.pop();
}
// recursive function to print the
// contents of a stack in reverse
private static void print(stack stack)
{
// if the stack is empty
if (stack.isempty())
return;
// get the top value
int value = stack.pop().value;
// recursive call
print(stack);
// print the popped value
system.out.print(value " ");
}
// driver code
public static void main(string[] args)
{
node root = new node(0);
root.left = new node(1);
root.right = new node(2);
root.left.left = new node(3);
root.left.right = new node(4);
root.right.left = new node(5);
root.right.right = new node(6);
root.left.left.left = new node(7);
root.left.right.left = new node(8);
root.left.right.right = new node(9);
// find and print the path
gfg pathbetweennodes = new gfg(root);
stack stack
= pathbetweennodes.pathbetweennode(7, 4);
print(stack);
}
}
python 3
# python3 implementation of
# the above approach
# a binary tree node
class node:
def __init__(self, value):
self.left = none
self.right = none
self.value = value
firstvaluefound = false
secondvaluefound = false
stack = []
root = none
# function to find the path
# between two nodes in binary
# tree
def pathbetweennode(v1, v2):
global firstvaluefound, secondvaluefound
pathbetweennode(root, v1, v2)
# if both the values are found
# then return the stack
if (firstvaluefound and
secondvaluefound):
return stack
# if none of the two values is
# found then return empty stack
return []
# function to find the path
# between two nodes in binary
# tree
def pathbetweennode(root,
v1, v2):
global firstvaluefound, secondvaluefound
# base condition
if (root == none):
return
# if both the values are found
# then return
if (firstvaluefound and
secondvaluefound):
return
# starting the stack frame with
# isaddedtostack = false flag
isaddedtostack = false
# if one of the value is found
# then add the value to the
# stack and make the isaddedtostack = true
if (firstvaluefound ^ secondvaluefound):
stack.append(root)
isaddedtostack = true
# if none of the two values
# is found
if (not (firstvaluefound and
secondvaluefound)):
pathbetweennode(root.left,
v1, v2)
# ccopy of current state of
# firstvaluefound and
# secondvaluefound flag
localfirstvaluefound = firstvaluefound
localsecondvaluefound = secondvaluefound
# if the first value is found
if (root.value == v1):
firstvaluefound = true
# if the second value is found
if (root.value == v2):
secondvaluefound = true
localadded = false
# if one of the value is found
# and the value was not added
# to the stack yet or there was
# only one value found and now
# both the values are found and
# was not added to the stack
# then add it
if (((firstvaluefound ^
secondvaluefound) or
((localfirstvaluefound ^
localsecondvaluefound) and
(firstvaluefound and
secondvaluefound))) and
not isaddedtostack):
localadded = true
stack.append(root)
# if none of the two values
# is found yet
if (not (firstvaluefound and
secondvaluefound)):
pathbetweennode(root.right,
v1, v2)
if ((firstvaluefound ^
secondvaluefound) and
not isaddedtostack and
not localadded):
stack.append(root)
if ((firstvaluefound ^
secondvaluefound) and
isaddedtostack):
stack.pop()
# recursive function to print
# the contents of a stack in
# reverse
def pri(stack):
# if the stack is empty
if (len(stack) == 0):
return
# get the top value
value = stack.pop().value
# recursive call
pri(stack)
# print the popped value
print(value, end = " ")
# driver code
if __name__ == "__main__":
root = node(0)
root.left = node(1)
root.right = node(2)
root.left.left = node(3)
root.left.right = node(4)
root.right.left = node(5)
root.right.right = node(6)
root.left.left.left = node(7)
root.left.right.left = node(8)
root.left.right.right = node(9)
# find and print the path
stack = pathbetweennode(7, 4)
pri(stack)
# this code is contributed by rutvik_56
c
// c# implementation of the approach
using system;
using system.collections;
using system.collections.generic;
class gfg
{
// a binary tree node
public class node
{
public node left;
public int value;
public node right;
public node(int value)
{
this.value = value;
left = null;
right = null;
}
}
private boolean firstvaluefound = false;
private boolean secondvaluefound = false;
private stack stack = new stack();
private node root = null;
public gfg(node root)
{
this.root = root;
}
// function to find the path between
// two nodes in binary tree
public stack pathbetweennode(int v1, int v2)
{
pathbetweennode(this.root, v1, v2);
// if both the values are found
// then return the stack
if (firstvaluefound && secondvaluefound)
{
return stack;
}
// if none of the two values is
// found then return empty stack
return new stack();
}
// function to find the path between
// two nodes in binary tree
private void pathbetweennode(node root, int v1, int v2)
{
// base condition
if (root == null)
return;
// if both the values are found then return
if (firstvaluefound && secondvaluefound)
return;
// starting the stack frame with
// isaddedtostack = false flag
boolean isaddedtostack = false;
// if one of the value is found then add the
// value to the stack and make the isaddedtostack = true
if (firstvaluefound ^ secondvaluefound)
{
stack.push(root);
isaddedtostack = true;
}
// if none of the two values is found
if (!(firstvaluefound && secondvaluefound))
{
pathbetweennode(root.left, v1, v2);
}
// ccopy of current state of firstvaluefound
// and secondvaluefound flag
boolean localfirstvaluefound = firstvaluefound;
boolean localsecondvaluefound = secondvaluefound;
// if the first value is found
if (root.value == v1)
firstvaluefound = true;
// if the second value is found
if (root.value == v2)
secondvaluefound = true;
boolean localadded = false;
// if one of the value is found and the value
// was not added to the stack yet or there was
// only one value found and now both the values
// are found and was not added to
// the stack then add it
if (((firstvaluefound ^ secondvaluefound)
|| ((localfirstvaluefound ^ localsecondvaluefound)
&& (firstvaluefound && secondvaluefound)))
&& !isaddedtostack)
{
localadded = true;
stack.push(root);
}
// if none of the two values is found yet
if (!(firstvaluefound && secondvaluefound))
{
pathbetweennode(root.right, v1, v2);
}
if ((firstvaluefound ^ secondvaluefound)
&& !isaddedtostack && !localadded)
stack.push(root);
if ((firstvaluefound ^ secondvaluefound)
&& isaddedtostack)
stack.pop();
}
// recursive function to print the
// contents of a stack in reverse
private static void print(stack stack)
{
// if the stack is empty
if (stack.count==0)
return;
// get the top value
int value = stack.pop().value;
// recursive call
print(stack);
// print the popped value
console.write(value " ");
}
// driver code
public static void main(string []args)
{
node root = new node(0);
root.left = new node(1);
root.right = new node(2);
root.left.left = new node(3);
root.left.right = new node(4);
root.right.left = new node(5);
root.right.right = new node(6);
root.left.left.left = new node(7);
root.left.right.left = new node(8);
root.left.right.right = new node(9);
// find and print the path
gfg pathbetweennodes = new gfg(root);
stack stack
= pathbetweennodes.pathbetweennode(7, 4);
print(stack);
}
}
// this code is contributed by arnab kundu
java 描述语言
output:
7 3 1 4
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
