#practiceLinkDiv { 표시: 없음 !중요; }이진 트리가 주어지면 연속적인 값을 갖는 노드로 구성된 가장 긴 경로의 길이를 오름차순으로 찾습니다. 모든 노드는 길이가 1인 경로로 간주됩니다.
예:
배쉬 문자열 길이
In below diagram binary tree with longest consecutive path(LCP) are shown :
위의 문제를 재귀적으로 해결할 수 있습니다. 각 노드에서 현재 노드의 값이 상위 노드보다 1 더 큰 경우 상위 노드에 대한 정보가 필요하며 각 노드에서 연속 경로를 만듭니다. 노드의 값을 상위 값과 비교하고 그에 따라 가장 긴 연속 경로를 업데이트합니다.
상위 노드의 값을 얻기 위해 (node_value + 1)을 재귀 메서드에 인수로 전달하고 연속 경로의 현재 길이 업데이트를 만족하면 노드 값을 이 인수 값과 비교하고 그렇지 않으면 현재 경로 길이를 1로 다시 초기화합니다.
더 나은 이해를 위해 아래 코드를 참조하십시오.
C++// C/C++ program to find longest consecutive // sequence in binary tree #include
// Java program to find longest consecutive // sequence in binary tree class Node { int data; Node left right; Node(int item) { data = item; left = right = null; } } class Result { int res = 0; } class BinaryTree { Node root; // method returns length of longest consecutive // sequence rooted at node root int longestConsecutive(Node root) { if (root == null) return 0; Result res = new Result(); // call utility method with current length 0 longestConsecutiveUtil(root 0 root.data res); return res.res; } // Utility method to return length of longest // consecutive sequence of tree private void longestConsecutiveUtil(Node root int curlength int expected Result res) { if (root == null) return; // if root data has one more than its parent // then increase current length if (root.data == expected) curlength++; else curlength = 1; // update the maximum by current length res.res = Math.max(res.res curlength); // recursively call left and right subtree with // expected value 1 more than root data longestConsecutiveUtil(root.left curlength root.data + 1 res); longestConsecutiveUtil(root.right curlength root.data + 1 res); } // Driver code public static void main(String args[]) { BinaryTree tree = new BinaryTree(); tree.root = new Node(6); tree.root.right = new Node(9); tree.root.right.left = new Node(7); tree.root.right.right = new Node(10); tree.root.right.right.right = new Node(11); System.out.println(tree.longestConsecutive(tree.root)); } } // This code is contributed by shubham96301
# Python3 program to find longest consecutive # sequence in binary tree # A utility class to create a node class newNode: def __init__(self data): self.data = data self.left = self.right = None # Utility method to return length of # longest consecutive sequence of tree def longestConsecutiveUtil(root curLength expected res): if (root == None): return # if root data has one more than its # parent then increase current length if (root.data == expected): curLength += 1 else: curLength = 1 # update the maximum by current length res[0] = max(res[0] curLength) # recursively call left and right subtree # with expected value 1 more than root data longestConsecutiveUtil(root.left curLength root.data + 1 res) longestConsecutiveUtil(root.right curLength root.data + 1 res) # method returns length of longest consecutive # sequence rooted at node root def longestConsecutive(root): if (root == None): return 0 res = [0] # call utility method with current length 0 longestConsecutiveUtil(root 0 root.data res) return res[0] # Driver Code if __name__ == '__main__': root = newNode(6) root.right = newNode(9) root.right.left = newNode(7) root.right.right = newNode(10) root.right.right.right = newNode(11) print(longestConsecutive(root)) # This code is contributed by PranchalK
// C# program to find longest consecutive // sequence in binary tree using System; class Node { public int data; public Node left right; public Node(int item) { data = item; left = right = null; } } class Result { public int res = 0; } class GFG { Node root; // method returns length of longest consecutive // sequence rooted at node root int longestConsecutive(Node root) { if (root == null) return 0; Result res = new Result(); // call utility method with current length 0 longestConsecutiveUtil(root 0 root.data res); return res.res; } // Utility method to return length of longest // consecutive sequence of tree private void longestConsecutiveUtil(Node root int curlength int expected Result res) { if (root == null) return; // if root data has one more than its parent // then increase current length if (root.data == expected) curlength++; else curlength = 1; // update the maximum by current length res.res = Math.Max(res.res curlength); // recursively call left and right subtree with // expected value 1 more than root data longestConsecutiveUtil(root.left curlength root.data + 1 res); longestConsecutiveUtil(root.right curlength root.data + 1 res); } // Driver code public static void Main(String []args) { GFG tree = new GFG(); tree.root = new Node(6); tree.root.right = new Node(9); tree.root.right.left = new Node(7); tree.root.right.right = new Node(10); tree.root.right.right.right = new Node(11); Console.WriteLine(tree.longestConsecutive(tree.root)); } } // This code is contributed by 29AjayKumar
<script> // JavaScript program to find longest consecutive // sequence in binary tree class Node { constructor(item) { this.data=item; this.left = this.right = null; } } let res = 0; let root; function longestConsecutive(root) { if (root == null) return 0; res=[0]; // call utility method with current length 0 longestConsecutiveUtil(root 0 root.data res); return res[0]; } // Utility method to return length of longest // consecutive sequence of tree function longestConsecutiveUtil(rootcurlength expectedres) { if (root == null) return; // if root data has one more than its parent // then increase current length if (root.data == expected) curlength++; else curlength = 1; // update the maximum by current length res[0] = Math.max(res[0] curlength); // recursively call left and right subtree with // expected value 1 more than root data longestConsecutiveUtil(root.left curlength root.data + 1 res); longestConsecutiveUtil(root.right curlength root.data + 1 res); } // Driver code root = new Node(6); root.right = new Node(9); root.right.left = new Node(7); root.right.right = new Node(10); root.right.right.right = new Node(11); document.write(longestConsecutive(root)); // This code is contributed by rag2127 </script>
산출
3
시간 복잡도: O(N) 여기서 N은 주어진 이진 트리의 노드 수입니다.
보조공간 : O(log(N))
아래 링크에서도 논의됩니다.
이진 트리의 최대 연속 증가 경로 길이
자바 스캐너