이진 트리의 최대 연속 증가 경로 길이

이진 트리가 주어지면 연속적인 값을 갖는 노드로 구성된 가장 긴 경로의 길이를 오름차순으로 찾습니다. 모든 노드는 길이가 1인 경로로 간주됩니다.

예:

 10 /  /  11 9 /  / /  /  13 12 13 8 Maximum Consecutive Path Length is 3 (10 11 12)   Note  : 10 9 8 is NOT considered since the nodes should be in increasing order. 5 /  /  8 11 /  /  9 10 / / / / 6 15 Maximum Consecutive Path Length is 2 (8 9).

이진 트리의 모든 노드는 상위 노드 중 하나에서 시작하는 경로의 일부가 되거나 이 노드 자체에서 새 경로가 시작될 수 있습니다. 핵심은 왼쪽 및 오른쪽 하위 트리의 경로 길이를 재귀적으로 찾은 다음 최대값을 반환하는 것입니다. 아래에서 설명하는 트리를 순회하는 동안 일부 경우를 고려해야 합니다.

이전 : 상위 노드의 값을 저장합니다. 루트에서 시작하는 경로의 길이가 최소 1이 될 수 있도록 루트 노드 값보다 하나 작은 값으로 prev를 초기화합니다.
오직 : 현재 방문한 노드의 상위에서 끝나는 경로 길이를 저장합니다.

사례 1 : 현재 노드의 값은 prev +1입니다.
이 경우 경로 길이를 1만큼 늘린 다음 왼쪽 및 오른쪽 하위 트리에 대한 경로 길이를 재귀적으로 찾은 다음 두 길이 사이의 최대값을 반환합니다.

사례 2 : 현재 노드의 값은 prev+1이 아닙니다.
새 경로는 이 노드에서 시작될 수 있으므로 왼쪽 및 오른쪽 하위 트리의 경로 길이를 재귀적으로 찾습니다. 현재 노드의 상위 노드에서 끝나는 경로는 이 노드에서 시작하는 경로보다 클 수 있습니다. 따라서 이 노드에서 시작하고 이전 노드에서 끝나는 경로의 최대값을 취합니다.

아래는 위의 아이디어를 구현한 것입니다.

C++

// C++ Program to find Maximum Consecutive // Path Length in a Binary Tree #include    using namespace std; // To represent a node of a Binary Tree struct Node {  Node *left *right;  int val; }; // Create a new Node and return its address Node *newNode(int val) {  Node *temp = new Node();  temp->val = val;  temp->left = temp->right = NULL;  return temp; } // Returns the maximum consecutive Path Length int maxPathLenUtil(Node *root int prev_val int prev_len) {  if (!root)  return prev_len;  // Get the value of Current Node  // The value of the current node will be  // prev Node for its left and right children  int cur_val = root->val;  // If current node has to be a part of the  // consecutive path then it should be 1 greater  // than the value of the previous node  if (cur_val == prev_val+1)  {  // a) Find the length of the Left Path  // b) Find the length of the Right Path  // Return the maximum of Left path and Right path  return max(maxPathLenUtil(root->left cur_val prev_len+1)  maxPathLenUtil(root->right cur_val prev_len+1));  }  // Find length of the maximum path under subtree rooted with this  // node (The path may or may not include this node)  int newPathLen = max(maxPathLenUtil(root->left cur_val 1)  maxPathLenUtil(root->right cur_val 1));  // Take the maximum previous path and path under subtree rooted  // with this node.  return max(prev_len newPathLen); } // A wrapper over maxPathLenUtil(). int maxConsecutivePathLength(Node *root) {  // Return 0 if root is NULL  if (root == NULL)  return 0;  // Else compute Maximum Consecutive Increasing Path  // Length using maxPathLenUtil.  return maxPathLenUtil(root root->val-1 0); } //Driver program to test above function int main() {  Node *root = newNode(10);  root->left = newNode(11);  root->right = newNode(9);  root->left->left = newNode(13);  root->left->right = newNode(12);  root->right->left = newNode(13);  root->right->right = newNode(8);  cout << 'Maximum Consecutive Increasing Path Length is '  << maxConsecutivePathLength(root);  return 0; }

Java

// Java Program to find Maximum Consecutive  // Path Length in a Binary Tree  import java.util.*; class GfG { // To represent a node of a Binary Tree  static class Node  {   Node left right;   int val;  } // Create a new Node and return its address  static Node newNode(int val)  {   Node temp = new Node();   temp.val = val;   temp.left = null;  temp.right = null;   return temp;  }  // Returns the maximum consecutive Path Length  static int maxPathLenUtil(Node root int prev_val int prev_len)  {   if (root == null)   return prev_len;   // Get the value of Current Node   // The value of the current node will be   // prev Node for its left and right children   int cur_val = root.val;   // If current node has to be a part of the   // consecutive path then it should be 1 greater   // than the value of the previous node   if (cur_val == prev_val+1)   {   // a) Find the length of the Left Path   // b) Find the length of the Right Path   // Return the maximum of Left path and Right path   return Math.max(maxPathLenUtil(root.left cur_val prev_len+1)   maxPathLenUtil(root.right cur_val prev_len+1));   }   // Find length of the maximum path under subtree rooted with this   // node (The path may or may not include this node)   int newPathLen = Math.max(maxPathLenUtil(root.left cur_val 1)   maxPathLenUtil(root.right cur_val 1));   // Take the maximum previous path and path under subtree rooted   // with this node.   return Math.max(prev_len newPathLen);  }  // A wrapper over maxPathLenUtil().  static int maxConsecutivePathLength(Node root)  {   // Return 0 if root is NULL   if (root == null)   return 0;   // Else compute Maximum Consecutive Increasing Path   // Length using maxPathLenUtil.   return maxPathLenUtil(root root.val-1 0);  }  //Driver program to test above function  public static void main(String[] args)  {   Node root = newNode(10);   root.left = newNode(11);   root.right = newNode(9);   root.left.left = newNode(13);   root.left.right = newNode(12);   root.right.left = newNode(13);   root.right.right = newNode(8);   System.out.println('Maximum Consecutive Increasing Path Length is '+maxConsecutivePathLength(root));  }  }

Python3

# Python program to find Maximum consecutive  # path length in binary tree # A binary tree node class Node: # Constructor to create a new node def __init__(self val): self.val = val self.left = None self.right = None # Returns the maximum consecutive path length def maxPathLenUtil(root prev_val prev_len): if root is None: return prev_len # Get the value of current node # The value of the current node will be  # prev node for its left and right children curr_val = root.val # If current node has to be a part of the  # consecutive path then it should be 1 greater # than the value of the previous node if curr_val == prev_val +1 : # a) Find the length of the left path  # b) Find the length of the right path # Return the maximum of left path and right path return max(maxPathLenUtil(root.left curr_val prev_len+1) maxPathLenUtil(root.right curr_val prev_len+1)) # Find the length of the maximum path under subtree  # rooted with this node newPathLen = max(maxPathLenUtil(root.left curr_val 1) maxPathLenUtil(root.right curr_val 1)) # Take the maximum previous path and path under subtree # rooted with this node return max(prev_len  newPathLen) # A Wrapper over maxPathLenUtil() def maxConsecutivePathLength(root): # Return 0 if root is None if root is None: return 0 # Else compute maximum consecutive increasing path  # length using maxPathLenUtil return maxPathLenUtil(root root.val -1  0) # Driver program to test above function root = Node(10) root.left = Node(11) root.right = Node(9) root.left.left = Node(13) root.left.right = Node(12) root.right.left = Node(13) root.right.right = Node(8) print ('Maximum Consecutive Increasing Path Length is') print (maxConsecutivePathLength(root)) # This code is contributed by Nikhil Kumar Singh(nickzuck_007)

// C# Program to find Maximum Consecutive  // Path Length in a Binary Tree using System; class GfG  {  // To represent a node of a Binary Tree   class Node   {   public Node left right;   public int val;   }  // Create a new Node and return its address   static Node newNode(int val)   {   Node temp = new Node();   temp.val = val;   temp.left = null;  temp.right = null;   return temp;   }   // Returns the maximum consecutive Path Length   static int maxPathLenUtil(Node root   int prev_val int prev_len)   {   if (root == null)   return prev_len;   // Get the value of Current Node   // The value of the current node will be   // prev Node for its left and right children   int cur_val = root.val;   // If current node has to be a part of the   // consecutive path then it should be 1 greater   // than the value of the previous node   if (cur_val == prev_val+1)   {   // a) Find the length of the Left Path   // b) Find the length of the Right Path   // Return the maximum of Left path and Right path   return Math.Max(maxPathLenUtil(root.left cur_val prev_len+1)   maxPathLenUtil(root.right cur_val prev_len+1));   }   // Find length of the maximum path under subtree rooted with this   // node (The path may or may not include this node)   int newPathLen = Math.Max(maxPathLenUtil(root.left cur_val 1)   maxPathLenUtil(root.right cur_val 1));   // Take the maximum previous path and path under subtree rooted   // with this node.   return Math.Max(prev_len newPathLen);   }   // A wrapper over maxPathLenUtil().   static int maxConsecutivePathLength(Node root)   {   // Return 0 if root is NULL   if (root == null)   return 0;   // Else compute Maximum Consecutive Increasing Path   // Length using maxPathLenUtil.   return maxPathLenUtil(root root.val - 1 0);   }   // Driver code  public static void Main(String[] args)   {   Node root = newNode(10);   root.left = newNode(11);   root.right = newNode(9);   root.left.left = newNode(13);   root.left.right = newNode(12);   root.right.left = newNode(13);   root.right.right = newNode(8);   Console.WriteLine('Maximum Consecutive' +  ' Increasing Path Length is '+  maxConsecutivePathLength(root));   }  }  // This code has been contributed by 29AjayKumar

JavaScript

<script> // Javascript Program to find Maximum Consecutive  // Path Length in a Binary Tree  // To represent a node of a Binary Tree  class Node  {  constructor(val)  {  this.val = val;  this.left = this.right = null;  } } // Returns the maximum consecutive Path Length  function maxPathLenUtil(rootprev_valprev_len) {  if (root == null)   return prev_len;     // Get the value of Current Node   // The value of the current node will be   // prev Node for its left and right children   let cur_val = root.val;     // If current node has to be a part of the   // consecutive path then it should be 1 greater   // than the value of the previous node   if (cur_val == prev_val+1)   {     // a) Find the length of the Left Path   // b) Find the length of the Right Path   // Return the maximum of Left path and Right path   return Math.max(maxPathLenUtil(root.left cur_val prev_len+1)   maxPathLenUtil(root.right cur_val prev_len+1));   }     // Find length of the maximum path under subtree rooted with this   // node (The path may or may not include this node)   let newPathLen = Math.max(maxPathLenUtil(root.left cur_val 1)   maxPathLenUtil(root.right cur_val 1));     // Take the maximum previous path and path under subtree rooted   // with this node.   return Math.max(prev_len newPathLen);  } // A wrapper over maxPathLenUtil().  function maxConsecutivePathLength(root) {  // Return 0 if root is NULL   if (root == null)   return 0;     // Else compute Maximum Consecutive Increasing Path   // Length using maxPathLenUtil.   return maxPathLenUtil(root root.val-1 0);  } // Driver program to test above function  let root = new Node(10);  root.left = new Node(11);  root.right = new Node(9);  root.left.left = new Node(13);  root.left.right = new Node(12);  root.right.left = new Node(13);  root.right.right = new Node(8);  document.write('Maximum Consecutive Increasing Path Length is '+  maxConsecutivePathLength(root)+'  
');  // This code is contributed by rag2127 </script>

산출

Maximum Consecutive Increasing Path Length is 3

시간 복잡도: O(n^2) 여기서 n은 주어진 이진 트리의 노드 수입니다.
보조 공간: O(log(n))