算法题：检查二叉树中的两个节点是否是表亲 |S2

2021年3月25日13:13:32 发表评论 947 次浏览

本文概述

给定一棵二叉树, 并且两个节点分别说" a"和" b", 请确定两个给定的节点是否互为表亲。

如果两个节点处于同一级别并且具有不同的父级, 则它们互为表亲。

例子:

6
   /   \
  3     5
 / \   / \
7   8 1   3
Say two node be 7 and 1, result is TRUE.
Say two nodes are 3 and 5, result is FALSE.
Say two nodes are 7 and 5, result is FALSE.

推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。

解决方案套装1已经讨论了通过执行二叉树遍历来发现给定节点是否为表亲。通过执行级别顺序遍历可以解决该问题。想法是使用队列执行级别顺序遍历, 其中每个队列元素是一对节点和该节点的父节点。对于按级别顺序遍历访问的每个节点, 请检查该节点是第一给定节点还是第二给定节点。如果找到任何节点, 则存储该节点的父节点。在执行级别顺序遍历时, 一次遍历一个级别。如果在给定级别找到两个节点, 则将比较它们的父值以检查它们是否为同级。如果在给定级别中找到一个节点, 而未找到另一个节点, 则给定节点不是表亲。

下面是上述方法的实现：

C ++

// CPP program to check if two Nodes in
// a binary tree are cousins
// using level-order traversals
#include <bits/stdc++.h>
using namespace std;
  
// A Binary Tree Node
struct Node {
     int data;
     struct Node *left, *right;
};
  
// A utility function to create a new
// Binary Tree Node
struct Node* newNode( int item)
{
     struct Node* temp = ( struct Node*) malloc ( sizeof ( struct Node));
     temp->data = item;
     temp->left = temp->right = NULL;
     return temp;
}
  
// Returns true if a and b are cousins, // otherwise false.
bool isCousin(Node* root, Node* a, Node* b)
{
     if (root == NULL)
         return false ;
  
     // To store parent of node a.
     Node* parA = NULL;
  
     // To store parent of node b.
     Node* parB = NULL;
  
     // queue to perform level order
     // traversal. Each element of
     // queue is a pair of node and
     // its parent.
     queue<pair<Node*, Node*> > q;
  
     // Dummy node to act like parent
     // of root node.
     Node* tmp = newNode(-1);
  
     // To store front element of queue.
     pair<Node*, Node*> ele;
  
     // Push root to queue.
     q.push(make_pair(root, tmp));
     int levSize;
  
     while (!q.empty()) {
  
         // find number of elements in
         // current level.
         levSize = q.size();
         while (levSize) {
  
             ele = q.front();
             q.pop();
  
             // check if current node is node a
             // or node b or not.
             if (ele.first->data == a->data) {
                 parA = ele.second;
             }
  
             if (ele.first->data == b->data) {
                 parB = ele.second;
             }
  
             // push children of current node
             // to queue.
             if (ele.first->left) {
                 q.push(make_pair(ele.first->left, ele.first));
             }
  
             if (ele.first->right) {
                 q.push(make_pair(ele.first->right, ele.first));
             }
  
             levSize--;
  
             // If both nodes are found in
             // current level then no need
             // to traverse current level further.
             if (parA && parB)
                 break ;
         }
  
         // Check if both nodes are siblings
         // or not.
         if (parA && parB) {
             return parA != parB;
         }
  
         // If one node is found in current level
         // and another is not found, then
         // both nodes are not cousins.
         if ((parA && !parB) || (parB && !parA)) {
             return false ;
         }
     }
  
     return false ;
}
// Driver Code
int main()
{
     /*
             1 
            /  \ 
           2    3
          / \  / \
         4   5 6  7
              \ \
              15 8
     */
  
     struct Node* root = newNode(1);
     root->left = newNode(2);
     root->right = newNode(3);
     root->left->left = newNode(4);
     root->left->right = newNode(5);
     root->left->right->right = newNode(15);
     root->right->left = newNode(6);
     root->right->right = newNode(7);
     root->right->left->right = newNode(8);
  
     struct Node *Node1, *Node2;
     Node1 = root->left->left;
     Node2 = root->right->right;
  
     isCousin(root, Node1, Node2) ? puts ( "Yes" ) : puts ( "No" );
  
     return 0;
}

Java

// Java program to check if two Nodes in
// a binary tree are cousins
// using level-order traversals
import java.util.*;
import javafx.util.Pair;
  
// User defined node class
class Node
{
     int data;
     Node left, right;
  
     // Constructor to create a new tree node 
     Node( int item)
     {
         data = item;
         left = right = null ;
     }
}
  
class BinaryTree
{
     Node root;
  
     // Returns true if a and b are cousins, // otherwise false. 
     boolean isCousin(Node node, Node a, Node b)
     {
         if (node == null )
             return false ;
          
         // To store parent of node a.
         Node parA = null ;
  
         // To store parent of node b.
         Node parB = null ;
  
         // queue to perform level order 
         // traversal. Each element of 
         // queue is a pair of node and 
         // its parent.
         Queue<Pair <Node, Node>> q = new LinkedList<> ();
  
         // Dummy node to act like parent 
         // of root node. 
         Node tmp = new Node(- 1 );
  
         // To store front element of queue. 
         Pair<Node, Node> ele;
  
         // Push root to queue.
         q.add( new Pair <Node, Node> (node, tmp));
  
         int levelSize;
  
         while (!q.isEmpty())
         {
  
             // find number of elements in 
             // current level. 
             levelSize = q.size();
             while (levelSize != 0 )
             {
                 ele = q.peek();
                 q.remove();
  
                 // check if current node is node a 
                 // or node b or not. 
                 if (ele.getKey().data == a.data)
                     parA = ele.getValue();
  
                 if (ele.getKey().data == b.data)
                     parB = ele.getValue();
  
                 // push children of current node 
                 // to queue. 
                 if (ele.getKey().left != null )
                     q.add( new Pair<Node, Node>(ele.getKey().left, ele.getKey()));
  
                 if (ele.getKey().right != null )
                     q.add( new Pair<Node, Node>(ele.getKey().right, ele.getKey()));
  
                 levelSize--;
  
                 // If both nodes are found in 
                 // current level then no need 
                 // to traverse current level further. 
                 if (parA != null && parB != null )
                     break ;
             }
  
             // Check if both nodes are siblings 
             // or not.
             if (parA != null && parB != null )
                 return parA != parB;
  
             // If one node is found in current level 
             // and another is not found, then 
             // both nodes are not cousins. 
             if ((parA!= null && parB== null ) || (parB!= null && parA== null ))
                 return false ;
         }
  
         return false ;
     }
  
     // Driver code
     public static void main(String args[])
     {
         BinaryTree tree = new BinaryTree();
         tree.root = new Node( 1 );
         tree.root.left = new Node( 2 );
         tree.root.right = new Node( 3 );
         tree.root.left.left = new Node( 4 );
         tree.root.left.right = new Node( 5 );
         tree.root.left.right.right = new Node( 15 );
         tree.root.right.left = new Node( 6 );
         tree.root.right.right = new Node( 7 );
         tree.root.right.left.right = new Node( 8 );
  
         Node Node1, Node2;
         Node1 = tree.root.left.right.right;
         Node2 = tree.root.right.left.right;
         if (tree.isCousin(tree.root, Node1, Node2))
             System.out.println( "Yes" );
         else
             System.out.println( "No" );
     }
}
  
// This code is contributed by shubham96301

Python3

# Python3 program to check if two 
# Nodes in a binary tree are cousins 
# using level-order traversals 
  
# A Binary Tree Node 
class Node:  
      
     def __init__( self , item):
         self .data = item
         self .left = None
         self .right = None
  
# Returns True if a and b 
# are cousins, otherwise False. 
def isCousin(root, a, b): 
   
     if root = = None :
         return False 
  
     # To store parent of node a. 
     parA = None 
  
     # To store parent of node b. 
     parB = None 
  
     # queue to perform level order 
     # traversal. Each element of queue 
     # is a pair of node and its parent. 
     q = [] 
  
     # Dummy node to act like 
     # parent of root node. 
     tmp = Node( - 1 ) 
  
     # Push root to queue. 
     q.append((root, tmp)) 
      
     while len (q) > 0 :  
  
         # find number of elements in 
         # current level. 
         levSize = len (q) 
         while levSize:  
  
             ele = q.pop( 0 ) 
  
             # check if current node is 
             # node a or node b or not. 
             if ele[ 0 ].data = = a.data:  
                 parA = ele[ 1 ] 
               
             if ele[ 0 ].data = = b.data:  
                 parB = ele[ 1 ] 
  
             # push children of 
             # current node to queue. 
             if ele[ 0 ].left:  
                 q.append((ele[ 0 ].left, ele[ 0 ])) 
               
             if ele[ 0 ].right:  
                 q.append((ele[ 0 ].right, ele[ 0 ])) 
             levSize - = 1
  
             # If both nodes are found in 
             # current level then no need 
             # to traverse current level further. 
             if parA and parB: 
                 break 
  
         # Check if both nodes 
         # are siblings or not. 
         if parA and parB:  
             return parA ! = parB 
  
         # If one node is found in current level 
         # and another is not found, then 
         # both nodes are not cousins. 
         if (parA and not parB) or (parB and not parA): 
             return False 
           
     return False 
   
# Driver Code 
if __name__ = = '__main__' :
  
     root = Node( 1 ) 
     root.left = Node( 2 ) 
     root.right = Node( 3 ) 
     root.left.left = Node( 4 ) 
     root.left.right = Node( 5 ) 
     root.left.right.right = Node( 15 ) 
     root.right.left = Node( 6 ) 
     root.right.right = Node( 7 ) 
     root.right.left.right = Node( 8 ) 
  
     Node1 = root.left.left 
     Node2 = root.right.right 
  
     if isCousin(root, Node1, Node2):
         print ( 'Yes' )
     else :
         print ( 'No' )
          
# This code is contributed by Rituraj Jain

C#

// C# program to check if two Nodes in
// a binary tree are cousins
// using level-order traversals
using System;
using System.Collections.Generic; 
  
// User defined node class
public class Node
{
     public int data;
     public Node left, right;
  
     // Constructor to create a new tree node 
     public Node( int item)
     {
         data = item;
         left = right = null ;
     }
}
// User defined pair class
public class Pair
{
  
     public Node first, second;
  
     // Constructor to create a new tree node 
     public Pair(Node first, Node second)
     {
         this .first = first;
         this .second = second;
     }
}
  
class BinaryTree
{
     Node root;
  
     // Returns true if a and b are cousins, // otherwise false. 
     Boolean isCousin(Node node, Node a, Node b)
     {
         if (node == null )
             return false ;
          
         // To store parent of node a.
         Node parA = null ;
  
         // To store parent of node b.
         Node parB = null ;
  
         // queue to perform level order 
         // traversal. Each element of 
         // queue is a pair of node and 
         // its parent.
         Queue<Pair > q = new Queue<Pair > ();
  
         // Dummy node to act like parent 
         // of root node. 
         Node tmp = new Node(-1);
  
         // To store front element of queue. 
         Pair ele;
  
         // Push root to queue.
         q.Enqueue( new Pair (node, tmp));
  
         int levelSize;
  
         while (q.Count>0)
         {
  
             // find number of elements in 
             // current level. 
             levelSize = q.Count;
             while (levelSize != 0)
             {
                 ele = q.Peek();
                 q.Dequeue();
  
                 // check if current node is node a 
                 // or node b or not. 
                 if (ele.first.data == a.data)
                     parA = ele.second;
  
                 if (ele.first.data == b.data)
                     parB = ele.second;
  
                 // push children of current node 
                 // to queue. 
                 if (ele.first.left != null )
                     q.Enqueue( new Pair(ele.first.left, ele.first));
  
                 if (ele.first.right != null )
                     q.Enqueue( new Pair(ele.first.right, ele.first));
  
                 levelSize--;
  
                 // If both nodes are found in 
                 // current level then no need 
                 // to traverse current level further. 
                 if (parA != null && parB != null )
                     break ;
             }
  
             // Check if both nodes are siblings 
             // or not.
             if (parA != null && parB != null )
                 return parA != parB;
  
             // If one node is found in current level 
             // and another is not found, then 
             // both nodes are not cousins. 
             if ((parA != null && parB == null ) || (parB != null && parA == null ))
                 return false ;
         }
  
         return false ;
     }
  
     // Driver code
     public static void Main(String []args)
     {
         BinaryTree tree = new BinaryTree();
         tree.root = new Node(1);
         tree.root.left = new Node(2);
         tree.root.right = new Node(3);
         tree.root.left.left = new Node(4);
         tree.root.left.right = new Node(5);
         tree.root.left.right.right = new Node(15);
         tree.root.right.left = new Node(6);
         tree.root.right.right = new Node(7);
         tree.root.right.left.right = new Node(8);
  
         Node Node1, Node2;
         Node1 = tree.root.left.right.right;
         Node2 = tree.root.right.left.right;
         if (tree.isCousin(tree.root, Node1, Node2))
             Console.WriteLine( "Yes" );
         else
             Console.WriteLine( "No" );
     }
}
  
// This code is contributed by Arnab Kundu

输出如下：

Yes

时间复杂度：O(n)

辅助空间：O(n)

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: