求二叉树的高度，因为只有偶数级上的节点才被视为有效的叶节点。 二叉树的高度是树的根和最远的叶子之间的边数。但是，如果我们改变了叶节点的定义，会怎么样呢。让我们将有效的叶节点定义为没有子节点且处于偶数级别的节点（将根节点视为奇数级别的节点）。
null
![图片[1]-仅考虑偶数水平叶的二叉树高度-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_xdfcg.png)
输出： 树的高度是4
解决方案： 解决这个问题的方法与正常的测高方法略有不同。在返回步骤中，我们检查节点是否为有效的根节点。如果有效，则返回1，否则返回0。现在在递归步骤中——如果左、右子树都产生0，那么当前节点也产生0，因为在这种情况下，从当前节点到有效叶节点没有路径。但是，如果子节点返回的值中至少有一个非零，这意味着该路径上的叶节点是有效的叶节点，因此该路径可以对最终结果做出贡献，因此我们为当前节点返回的最大值为+1。
![图片[2]-仅考虑偶数水平叶的二叉树高度-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_s1-1.png)
C++
/* Program to find height of the tree considering only even level leaves. */ #include <bits/stdc++.h> using namespace std; /* A binary tree node has data, pointer to left child and a pointer to right child */ struct Node { int data; struct Node* left; struct Node* right; }; int heightOfTreeUtil(Node* root, bool isEven) { // Base Case if (!root) return 0; if (!root->left && !root->right) { if (isEven) return 1; else return 0; } /*left stores the result of left subtree, and right stores the result of right subtree*/ int left = heightOfTreeUtil(root->left, !isEven); int right = heightOfTreeUtil(root->right, !isEven); /*If both left and right returns 0, it means there is no valid path till leaf node*/ if (left == 0 && right == 0) return 0; return (1 + max(left, right)); } /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ struct Node* newNode( int data) { struct Node* node = ( struct Node*) malloc ( sizeof ( struct Node)); node->data = data; node->left = NULL; node->right = NULL; return (node); } int heightOfTree(Node* root) { return heightOfTreeUtil(root, false ); } /* Driver program to test above functions*/ int main() { // Let us create binary tree shown in above diagram 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->left = newNode(6); cout << "Height of tree is " << heightOfTree(root); return 0; } |
JAVA
/* Java Program to find height of the tree considering only even level leaves. */ class GfG { /* A binary tree node has data, pointer to left child and a pointer to right child */ static class Node { int data; Node left; Node right; } static int heightOfTreeUtil(Node root, boolean isEven) { // Base Case if (root == null ) return 0 ; if (root.left == null && root.right == null ) { if (isEven == true ) return 1 ; else return 0 ; } /*left stores the result of left subtree, and right stores the result of right subtree*/ int left = heightOfTreeUtil(root.left, !isEven); int right = heightOfTreeUtil(root.right, !isEven); /*If both left and right returns 0, it means there is no valid path till leaf node*/ if (left == 0 && right == 0 ) return 0 ; return ( 1 + Math.max(left, right)); } /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ static Node newNode( int data) { Node node = new Node(); node.data = data; node.left = null ; node.right = null ; return (node); } static int heightOfTree(Node root) { return heightOfTreeUtil(root, false ); } /* Driver program to test above functions*/ public static void main(String[] args) { // Let us create binary tree shown in above diagram 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.left = newNode( 6 ); System.out.println( "Height of tree is " + heightOfTree(root)); } } |
Python3
# Program to find height of the tree considering # only even level leaves. # Helper class that allocates a new node with the # given data and None left and right pointers. class newNode: def __init__( self , data): self .data = data self .left = None self .right = None def heightOfTreeUtil(root, isEven): # Base Case if ( not root): return 0 if ( not root.left and not root.right): if (isEven): return 1 else : return 0 # left stores the result of left subtree, # and right stores the result of right subtree left = heightOfTreeUtil(root.left, not isEven) right = heightOfTreeUtil(root.right, not isEven) #If both left and right returns 0, it means # there is no valid path till leaf node if (left = = 0 and right = = 0 ): return 0 return ( 1 + max (left, right)) def heightOfTree(root): return heightOfTreeUtil(root, False ) # Driver Code if __name__ = = '__main__' : # Let us create binary tree shown # in above diagram root = newNode( 1 ) root.left = newNode( 2 ) root.right = newNode( 3 ) root.left.left = newNode( 4 ) root.left.right = newNode( 5 ) root.left.right.left = newNode( 6 ) print ( "Height of tree is" , heightOfTree(root)) # This code is contributed by PranchalK |
C#
/* C# Program to find height of the tree considering only even level leaves. */ using System; class GfG { /* A binary tree node has data, pointer to left child and a pointer to right child */ class Node { public int data; public Node left; public Node right; } static int heightOfTreeUtil(Node root, bool isEven) { // Base Case if (root == null ) return 0; if (root.left == null && root.right == null ) { if (isEven == true ) return 1; else return 0; } /*left stores the result of left subtree, and right stores the result of right subtree*/ int left = heightOfTreeUtil(root.left, !isEven); int right = heightOfTreeUtil(root.right, !isEven); /*If both left and right returns 0, it means there is no valid path till leaf node*/ if (left == 0 && right == 0) return 0; return (1 + Math.Max(left, right)); } /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ static Node newNode( int data) { Node node = new Node(); node.data = data; node.left = null ; node.right = null ; return (node); } static int heightOfTree(Node root) { return heightOfTreeUtil(root, false ); } /* Driver code*/ public static void Main(String[] args) { // Let us create binary tree // shown in above diagram 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.left = newNode(6); Console.WriteLine( "Height of tree is " + heightOfTree(root)); } } /* This code is contributed by Rajput-Ji*/ |
Javascript
<script> /* javascript Program to find height of the tree considering only even level leaves. */ /* * A binary tree node has data, pointer to left child and a pointer to right * child */ class Node { constructor(val) { this .data = val; this .left = null ; this .right = null ; } } function heightOfTreeUtil(root, isEven) { // Base Case if (root == null ) return 0; if (root.left == null && root.right == null ) { if (isEven == true ) return 1; else return 0; } /* * left stores the result of left subtree, and right stores the result of right * subtree */ var left = heightOfTreeUtil(root.left, !isEven); var right = heightOfTreeUtil(root.right, !isEven); /* * If both left and right returns 0, it means there is no valid path till leaf * node */ if (left == 0 && right == 0) return 0; return (1 + Math.max(left, right)); } /* * Helper function that allocates a new node with the given data and NULL left * and right pointers. */ function newNode(data) { var node = new Node(); node.data = data; node.left = null ; node.right = null ; return (node); } function heightOfTree(root) { return heightOfTreeUtil(root, false ); } /* Driver program to test above functions */ // Let us create binary tree shown in above diagram var root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.left.right.left = newNode(6); document.write( "Height of tree is " + heightOfTree(root)); // This code is contributed by umadevi9616 </script> |
输出：
Height of tree is 4
时间复杂性： O（n），其中n是给定二叉树中的节点数。
?list=PLqM7alHXFySHCXD7r1J0ky9Zg_GBB1dbk
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
