给定一棵二叉树，求其中所有左叶的和。例如，下面的二叉树中所有左叶的总和为5+1=6。
null
![图片[1]-求给定二叉树中所有左叶的和-yiteyi-C++库](https://media.geeksforgeeks.org/wp-content/uploads/20200930191310/MaxHeap.jpg)
这个想法是从树根开始遍历树。对于每个节点，检查其左子树是否为叶。如果是，则将其添加到结果中。 以下是上述理念的实施。
C++
// A C++ program to find sum of all left leaves #include <bits/stdc++.h> using namespace std; /* A binary tree Node has key, pointer to left and right children */ struct Node { int key; struct Node* left, *right; }; /* Helper function that allocates a new node with the given data and NULL left and right pointer. */ Node *newNode( char k) { Node *node = new Node; node->key = k; node->right = node->left = NULL; return node; } // A utility function to check if a given node is leaf or not bool isLeaf(Node *node) { if (node == NULL) return false ; if (node->left == NULL && node->right == NULL) return true ; return false ; } // This function returns sum of all left leaves in a given // binary tree int leftLeavesSum(Node *root) { // Initialize result int res = 0; // Update result if root is not NULL if (root != NULL) { // If left of root is NULL, then add key of // left child if (isLeaf(root->left)) res += root->left->key; else // Else recur for left child of root res += leftLeavesSum(root->left); // Recur for right child of root and update res res += leftLeavesSum(root->right); } // return result return res; } /* Driver program to test above functions*/ int main() { // Let us a construct the Binary Tree struct Node *root = newNode(20); root->left = newNode(9); root->right = newNode(49); root->right->left = newNode(23); root->right->right = newNode(52); root->right->right->left = newNode(50); root->left->left = newNode(5); root->left->right = newNode(12); root->left->right->right = newNode(12); cout << "Sum of left leaves is " << leftLeavesSum(root); return 0; } |
JAVA
// Java program to find sum of all left leaves class Node { int data; Node left, right; Node( int item) { data = item; left = right = null ; } } class BinaryTree { Node root; // A utility function to check if a given node is leaf or not boolean isLeaf(Node node) { if (node == null ) return false ; if (node.left == null && node.right == null ) return true ; return false ; } // This function returns sum of all left leaves in a given // binary tree int leftLeavesSum(Node node) { // Initialize result int res = 0 ; // Update result if root is not NULL if (node != null ) { // If left of root is NULL, then add key of // left child if (isLeaf(node.left)) res += node.left.data; else // Else recur for left child of root res += leftLeavesSum(node.left); // Recur for right child of root and update res res += leftLeavesSum(node.right); } // return result return res; } // Driver program public static void main(String args[]) { BinaryTree tree = new BinaryTree(); tree.root = new Node( 20 ); tree.root.left = new Node( 9 ); tree.root.right = new Node( 49 ); tree.root.left.right = new Node( 12 ); tree.root.left.left = new Node( 5 ); tree.root.right.left = new Node( 23 ); tree.root.right.right = new Node( 52 ); tree.root.left.right.right = new Node( 12 ); tree.root.right.right.left = new Node( 50 ); System.out.println( "The sum of leaves is " + tree.leftLeavesSum(tree.root)); } } // This code is contributed by Mayank Jaiswal |
Python3
# Python program to find sum of all left leaves # A Binary tree node class Node: # Constructor to create a new Node def __init__( self , key): self .key = key self .left = None self .right = None # A utility function to check if a given node is leaf or not def isLeaf(node): if node is None : return False if node.left is None and node.right is None : return True return False # This function return sum of all left leaves in a # given binary tree def leftLeavesSum(root): # Initialize result res = 0 # Update result if root is not None if root is not None : # If left of root is None, then add key of # left child if isLeaf(root.left): res + = root.left.key else : # Else recur for left child of root res + = leftLeavesSum(root.left) # Recur for right child of root and update res res + = leftLeavesSum(root.right) return res # Driver program to test above function # Let us construct the Binary Tree shown in the above function root = Node( 20 ) root.left = Node( 9 ) root.right = Node( 49 ) root.right.left = Node( 23 ) root.right.right = Node( 52 ) root.right.right.left = Node( 50 ) root.left.left = Node( 5 ) root.left.right = Node( 12 ) root.left.right.right = Node( 12 ) print ( "Sum of left leaves is" , leftLeavesSum(root)) # This code is contributed by Nikhil Kumar Singh(nickzuck_007) |
C#
using System; // C# program to find sum of all left leaves public class Node { public int data; public Node left, right; public Node( int item) { data = item; left = right = null ; } } public class BinaryTree { public Node root; // A utility function to check if a given node is leaf or not public virtual bool isLeaf(Node node) { if (node == null ) { return false ; } if (node.left == null && node.right == null ) { return true ; } return false ; } // This function returns sum of all left leaves in a given // binary tree public virtual int leftLeavesSum(Node node) { // Initialize result int res = 0; // Update result if root is not NULL if (node != null ) { // If left of root is NULL, then add key of // left child if (isLeaf(node.left)) { res += node.left.data; } else // Else recur for left child of root { res += leftLeavesSum(node.left); } // Recur for right child of root and update res res += leftLeavesSum(node.right); } // return result return res; } // Driver program public static void Main( string [] args) { BinaryTree tree = new BinaryTree(); tree.root = new Node(20); tree.root.left = new Node(9); tree.root.right = new Node(49); tree.root.left.right = new Node(12); tree.root.left.left = new Node(5); tree.root.right.left = new Node(23); tree.root.right.right = new Node(52); tree.root.left.right.right = new Node(12); tree.root.right.right.left = new Node(50); Console.WriteLine( "The sum of leaves is " + tree.leftLeavesSum(tree.root)); } } // This code is contributed by Shrikant13 |
Javascript
<script> // Javascript program to find sum of all left leaves class Node { constructor(k) { this .data = k; this .left = null ; this .right = null ; } } // A utility function to check if a given node is leaf or not function isLeaf(node) { if (node == null ) return false ; if (node.left == null && node.right == null ) return true ; return false ; } // This function returns sum of all left leaves in a given // binary tree function leftLeavesSum(node) { // Initialize result let res = 0; // Update result if root is not NULL if (node != null ) { // If left of root is NULL, then add key of // left child if (isLeaf(node.left)) res += node.left.data; else // Else recur for left child of root res += leftLeavesSum(node.left); // Recur for right child of root and update res res += leftLeavesSum(node.right); } // return result return res; } // Driver program root = new Node(20); root.left = new Node(9); root.right = new Node(49); root.left.right = new Node(12); root.left.left = new Node(5); root.right.left = new Node(23); root.right.right = new Node(52); root.left.right.right = new Node(12); root.right.right.left = new Node(50); document.write( "The sum of leaves is " +leftLeavesSum(root)); // This code is contributed by unknown2108 </script> |
输出
Sum of left leaves is 78
时间复杂性： O（N），其中N是二叉树中的节点数。
下面是解决上述问题的另一种方法。这个解作为累加器传入一个和变量。当遇到左叶时，将该叶的数据添加到总和中。该方法的时间复杂度也是O（n）。感谢Xin Tong（Geeksforgeks userid trent.Tong）提出了这种方法。
C++
// A C++ program to find sum of all left leaves #include <bits/stdc++.h> using namespace std; /* A binary tree Node has key, pointer to left and right children */ struct Node { int key; struct Node* left, *right; }; /* Helper function that allocates a new node with the given data and NULL left and right pointer. */ Node *newNode( char k) { Node *node = new Node; node->key = k; node->right = node->left = NULL; return node; } /* Pass in a sum variable as an accumulator */ void leftLeavesSumRec(Node *root, bool isleft, int *sum) { if (!root) return ; // Check whether this node is a leaf node and is left. if (!root->left && !root->right && isleft) *sum += root->key; // Pass 1 for left and 0 for right leftLeavesSumRec(root->left, 1, sum); leftLeavesSumRec(root->right, 0, sum); } // A wrapper over above recursive function int leftLeavesSum(Node *root) { int sum = 0; //Initialize result // use the above recursive function to evaluate sum leftLeavesSumRec(root, 0, &sum); return sum; } /* Driver program to test above functions*/ int main() { // Let us construct the Binary Tree shown in the // above figure int sum = 0; struct Node *root = newNode(20); root->left = newNode(9); root->right = newNode(49); root->right->left = newNode(23); root->right->right = newNode(52); root->right->right->left = newNode(50); root->left->left = newNode(5); root->left->right = newNode(12); root->left->right->right = newNode(12); cout << "Sum of left leaves is " << leftLeavesSum(root) << endl; return 0; } |
JAVA
// Java program to find sum of all left leaves class Node { int data; Node left, right; Node( int item) { data = item; left = right = null ; } } // Passing sum as accumulator and implementing pass by reference // of sum variable class Sum { int sum = 0 ; } class BinaryTree { Node root; /* Pass in a sum variable as an accumulator */ void leftLeavesSumRec(Node node, boolean isleft, Sum summ) { if (node == null ) return ; // Check whether this node is a leaf node and is left. if (node.left == null && node.right == null && isleft) summ.sum = summ.sum + node.data; // Pass true for left and false for right leftLeavesSumRec(node.left, true , summ); leftLeavesSumRec(node.right, false , summ); } // A wrapper over above recursive function int leftLeavesSum(Node node) { Sum suum = new Sum(); // use the above recursive function to evaluate sum leftLeavesSumRec(node, false , suum); return suum.sum; } // Driver program public static void main(String args[]) { BinaryTree tree = new BinaryTree(); tree.root = new Node( 20 ); tree.root.left = new Node( 9 ); tree.root.right = new Node( 49 ); tree.root.left.right = new Node( 12 ); tree.root.left.left = new Node( 5 ); tree.root.right.left = new Node( 23 ); tree.root.right.right = new Node( 52 ); tree.root.left.right.right = new Node( 12 ); tree.root.right.right.left = new Node( 50 ); System.out.println( "The sum of leaves is " + tree.leftLeavesSum(tree.root)); } } // This code is contributed by Mayank Jaiswal |
Python3
# Python program to find sum of all left leaves # A binary tree node class Node: # A constructor to create a new Node def __init__( self , key): self .key = key self .left = None self .right = None def leftLeavesSumRec(root, isLeft, summ): if root is None : return # Check whether this node is a leaf node and is left if root.left is None and root.right is None and isLeft = = True : summ[ 0 ] + = root.key # Pass 1 for left and 0 for right leftLeavesSumRec(root.left, 1 , summ) leftLeavesSumRec(root.right, 0 , summ) # A wrapper over above recursive function def leftLeavesSum(root): summ = [ 0 ] # initialize result # Use the above recursive function to evaluate sum leftLeavesSumRec(root, 0 , summ) return summ[ 0 ] # Driver program to test above function # Let us construct the Binary Tree shown in the # above figure root = Node( 20 ); root.left = Node( 9 ); root.right = Node( 49 ); root.right.left = Node( 23 ); root.right.right = Node( 52 ); root.right.right.left = Node( 50 ); root.left.left = Node( 5 ); root.left.right = Node( 12 ); root.left.right.right = Node( 12 ); print ( "Sum of left leaves is" , leftLeavesSum(root)) # This code is contributed by Nikhil Kumar Singh(nickzuck_007) |
C#
using System; // C# program to find sum of all left leaves public class Node { public int data; public Node left, right; public Node( int item) { data = item; left = right = null ; } } // Passing sum as accumulator and implementing pass by reference // of sum variable public class Sum { public int sum = 0; } public class BinaryTree { public Node root; /* Pass in a sum variable as an accumulator */ public virtual void leftLeavesSumRec(Node node, bool isleft, Sum summ) { if (node == null ) { return ; } // Check whether this node is a leaf node and is left. if (node.left == null && node.right == null && isleft) { summ.sum = summ.sum + node.data; } // Pass true for left and false for right leftLeavesSumRec(node.left, true , summ); leftLeavesSumRec(node.right, false , summ); } // A wrapper over above recursive function public virtual int leftLeavesSum(Node node) { Sum suum = new Sum(); // use the above recursive function to evaluate sum leftLeavesSumRec(node, false , suum); return suum.sum; } // Driver program public static void Main( string [] args) { BinaryTree tree = new BinaryTree(); tree.root = new Node(20); tree.root.left = new Node(9); tree.root.right = new Node(49); tree.root.left.right = new Node(12); tree.root.left.left = new Node(5); tree.root.right.left = new Node(23); tree.root.right.right = new Node(52); tree.root.left.right.right = new Node(12); tree.root.right.right.left = new Node(50); Console.WriteLine( "The sum of leaves is " + tree.leftLeavesSum(tree.root)); } } // This code is contributed by Shrikant13 |
Javascript
<script> // javascript program to find sum of all left leaves class Node { constructor(item) { this .data = item; this .left = this .right = null ; } } // Passing sum as accumulator and implementing pass by reference // of sum variable class Sum { constructor(){ this .sum = 0; } } var root; /* Pass in a sum variable as an accumulator */ function leftLeavesSumRec( node, isleft, summ) { if (node == null ) return ; // Check whether this node is a leaf node and is left. if (node.left == null && node.right == null && isleft) summ.sum = summ.sum + node.data; // Pass true for left and false for right leftLeavesSumRec(node.left, true , summ); leftLeavesSumRec(node.right, false , summ); } // A wrapper over above recursive function function leftLeavesSum( node) { suum = new Sum(); // use the above recursive function to evaluate sum leftLeavesSumRec(node, false , suum); return suum.sum; } // Driver program root = new Node(20); root.left = new Node(9); root.right = new Node(49); root.left.right = new Node(12); root.left.left = new Node(5); root.right.left = new Node(23); root.right.right = new Node(52); root.left.right.right = new Node(12); root.right.right.left = new Node(50); document.write( "The sum of leaves is " + leftLeavesSum(root)); // This code contributed by gauravrajput1 </script> |
输出
Sum of left leaves is 78
下面是解决上述问题的另一种方法。我们可以在函数中将bool作为参数传递，以检查它是左节点还是右节点。该方法的时间复杂度也是O（n）。
C
#include <stdbool.h> #include <stdio.h> #include <stdlib.h> struct Node { int data; struct Node* left; struct Node* right; }; typedef struct Node str_node; str_node* create( int item); int sumAllLeaftLeaves(str_node* node, bool isLeft); int main( void ) { int d = 0; str_node* root = create(20); root->left = create(9); root->right = create(49); root->right->left = create(23); root->right->right = create(52); root->right->right->left = create(50); root->left->left = create(5); root->left->right = create(12); root->left->right->right = create(12); printf ( "Sum of left leaves is: %d " , sumAllLeaftLeaves(root, false )); return 0; } str_node* create( int item) { str_node* newnode = (str_node*) malloc ( sizeof (str_node)); newnode->data = item; newnode->left = NULL; newnode->right = NULL; return newnode; } int sumAllLeaftLeaves(str_node* node, bool isLeft) { // base case: if (node == NULL) return 0; // check whether this node is a leaf node and is left. if (node->left == NULL && node->right == NULL && isLeft) return node->data; // recursive case return sumAllLeaftLeaves(node->left, true ) + sumAllLeaftLeaves(node->right, false ); } |
JAVA
class GFG{ static class Node { int data; Node left; Node right; }; static Node str_node; static Node create( int item) { Node newnode = new Node(); newnode.data = item; newnode.left = null ; newnode.right = null ; return newnode; } static int sumAllLeaftLeaves(Node node, boolean isLeft) { // base case: if (node == null ) return 0 ; // check whether this node is a leaf node and is left. if (node.left == null && node.right == null && isLeft) return node.data; // recursive case return sumAllLeaftLeaves(node.left, true ) + sumAllLeaftLeaves(node.right, false ); } public static void main(String[] args) { int d = 0 ; Node root = create( 20 ); root.left = create( 9 ); root.right = create( 49 ); root.right.left = create( 23 ); root.right.right = create( 52 ); root.right.right.left = create( 50 ); root.left.left = create( 5 ); root.left.right = create( 12 ); root.left.right.right = create( 12 ); System.out.printf( "Sum of left leaves is: %d " , sumAllLeaftLeaves(root, false )); } } // This code is contributed by umadevi9616 |
输出：
Sum of left leaves is 78
迭代方法： 这是求左叶和的迭代方法。 其思想是使用堆栈在树上执行深度优先遍历（按顺序、按前顺序或按后顺序），并检查左边的子节点是否是叶节点。如果是，则将节点值添加到sum变量中
C++
// C++ program to find sum of all left leaves #include<bits/stdc++.h> using namespace std; // A binary tree node class Node { public : int key; Node* left, *right; // A constructor to create a new Node Node( int key_) { key = key_; left = NULL; right = NULL; } }; // Return the sum of left leaf nodes int sumOfLeftLeaves(Node* root) { if (root == NULL) return 0; // Using a stack_ for Depth-First // Traversal of the tree stack<Node*> stack_; stack_.push(root); // sum holds the sum of all the left leaves int sum = 0; while (stack_.size() > 0) { Node* currentNode = stack_.top(); stack_.pop(); if (currentNode->left != NULL) { stack_.push(currentNode->left); // Check if currentNode's left // child is a leaf node if (currentNode->left->left == NULL && currentNode->left->right == NULL) { // if currentNode is a leaf, // add its data to the sum sum = sum + currentNode->left->key ; } } if (currentNode->right != NULL) stack_.push(currentNode->right); } return sum; } // Driver Code int main() { Node *root = new Node(20); root->left= new Node(9); root->right = new Node(49); root->right->left = new Node(23); root->right->right= new Node(52); root->right->right->left = new Node(50); root->left->left = new Node(5); root->left->right = new Node(12); root->left->right->right = new Node(12); cout << "Sum of left leaves is " << sumOfLeftLeaves(root) << endl; return 0; } // This code is contributed by Arnab Kundu |
JAVA
// Java program to find sum of all left leaves import java.util.*; class GFG { // A binary tree node static class Node { int key; Node left, right; // A constructor to create a new Node Node( int key_) { this .key = key_; this .left = null ; this .right = null ; } }; // Return the sum of left leaf nodes static int sumOfLeftLeaves(Node root) { if (root == null ) return 0 ; // Using a stack_ for Depth-First // Traversal of the tree Stack<Node> stack_ = new Stack<>(); stack_.push(root); // sum holds the sum of all the left leaves int sum = 0 ; while (stack_.size() > 0 ) { Node currentNode = stack_.peek(); stack_.pop(); if (currentNode.left != null ) { stack_.add(currentNode.left); // Check if currentNode's left // child is a leaf node if (currentNode.left.left == null && currentNode.left.right == null ) { // if currentNode is a leaf, // add its data to the sum sum = sum + currentNode.left.key ; } } if (currentNode.right != null ) stack_.add(currentNode.right); } return sum; } // Driver Code public static void main(String[] args) { Node root = new Node( 20 ); root.left= new Node( 9 ); root.right = new Node( 49 ); root.right.left = new Node( 23 ); root.right.right= new Node( 52 ); root.right.right.left = new Node( 50 ); root.left.left = new Node( 5 ); root.left.right = new Node( 12 ); root.left.right.right = new Node( 12 ); System.out.print( "Sum of left leaves is " + sumOfLeftLeaves(root) + "" ); } } // This code is contributed by aashish1995 |
Python3
# Python3 program to find sum of all left leaves # A binary tree node class Node: # A constructor to create a new Node def __init__( self , key): self .data = key self .left = None self .right = None # Return the sum of left leaf nodes def sumOfLeftLeaves(root): if (root is None ): return # Using a stack for Depth-First Traversal of the tree stack = [] stack.append(root) # sum holds the sum of all the left leaves sum = 0 while len (stack) > 0 : currentNode = stack.pop() if currentNode.left is not None : stack.append(currentNode.left) # Check if currentNode's left child is a leaf node if currentNode.left.left is None and currentNode.left.right is None : # if currentNode is a leaf, add its data to the sum sum = sum + currentNode.left.data if currentNode.right is not None : stack.append(currentNode.right) return sum # Driver Code root = Node( 20 ); root.left = Node( 9 ); root.right = Node( 49 ); root.right.left = Node( 23 ); root.right.right = Node( 52 ); root.right.right.left = Node( 50 ); root.left.left = Node( 5 ); root.left.right = Node( 12 ); root.left.right.right = Node( 12 ); print ( 'Sum of left leaves is {}' . format (sumOfLeftLeaves(root))) |
C#
// C# program to find sum of all left leaves using System; using System.Collections.Generic; class GFG { // A binary tree node public class Node { public int key; public Node left, right; // A constructor to create a new Node public Node( int key_) { this .key = key_; this .left = null ; this .right = null ; } }; // Return the sum of left leaf nodes static int sumOfLeftLeaves(Node root) { if (root == null ) return 0; // Using a stack_ for Depth-First // Traversal of the tree Stack<Node> stack_ = new Stack<Node>(); stack_.Push(root); // sum holds the sum of all the left leaves int sum = 0; while (stack_.Count > 0) { Node currentNode = stack_.Peek(); stack_.Pop(); if (currentNode.left != null ) { stack_.Push(currentNode.left); // Check if currentNode's left // child is a leaf node if (currentNode.left.left == null && currentNode.left.right == null ) { // if currentNode is a leaf, // add its data to the sum sum = sum + currentNode.left.key ; } } if (currentNode.right != null ) stack_.Push(currentNode.right); } return sum; } // Driver Code public static void Main(String[] args) { Node root = new Node(20); root.left= new Node(9); root.right = new Node(49); root.right.left = new Node(23); root.right.right= new Node(52); root.right.right.left = new Node(50); root.left.left = new Node(5); root.left.right = new Node(12); root.left.right.right = new Node(12); Console.Write( "Sum of left leaves is " + sumOfLeftLeaves(root) + "" ); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript program to find sum of all left leaves // A binary tree node class Node { // A constructor to create a new Node constructor(key_) { this .key = key_; this .left = null ; this .right = null ; } }; // Return the sum of left leaf nodes function sumOfLeftLeaves(root) { if (root == null ) return 0; // Using a stack_ for Depth-First // Traversal of the tree var stack_ = []; stack_.push(root); // sum holds the sum of all the left leaves var sum = 0; while (stack_.length > 0) { var currentNode = stack_[stack_.length-1]; stack_.pop(); if (currentNode.left != null ) { stack_.push(currentNode.left); // Check if currentNode's left // child is a leaf node if (currentNode.left.left == null && currentNode.left.right == null ) { // if currentNode is a leaf, // add its data to the sum sum = sum + currentNode.left.key ; } } if (currentNode.right != null ) stack_.push(currentNode.right); } return sum; } // Driver Code var root = new Node(20); root.left= new Node(9); root.right = new Node(49); root.right.left = new Node(23); root.right.right= new Node(52); root.right.right.left = new Node(50); root.left.left = new Node(5); root.left.right = new Node(12); root.left.right.right = new Node(12); document.write( "Sum of left leaves is " + sumOfLeftLeaves(root) + "<br>" ); </script> |
输出
Sum of left leaves is 78
幸亏 Shubham Tambere 感谢你提出这种方法。
BFS方法： 我们能行 BFS遍历 并保留一个单独的变量来表示它是节点的左子节点还是右子节点。一旦我们遇到一片叶子，我们就会检查它是其父的左子叶还是其父的右子叶。如果它是一个左撇子，我们在总和中加上它的值。
以下是上述方法的实施情况：
C++
// C++ program to find sum of all left leaves #include <bits/stdc++.h> using namespace std; // A binary tree node class Node { public : int key; Node *left, *right; // constructor to create a new Node Node( int key_) { key = key_; left = NULL; right = NULL; } }; // Return the sum of left leaf nodes int sumOfLeftLeaves(Node* root) { if (root == NULL) return 0; // A queue of pairs to do bfs traversal // and keep track if the node is a left // or right child if boolean value // is true then it is a left child. queue<pair<Node*, bool > > q; q.push({ root, 0 }); int sum = 0; // do bfs traversal while (!q.empty()) { Node* temp = q.front().first; bool is_left_child = q.front().second; q.pop(); // if temp is a leaf node and // left child of its parent if (!temp->left && !temp->right && is_left_child) sum = sum + temp->key; // if it is not leaf then // push its children nodes // into queue if (temp->left) { // boolean value is true // here because it is left // child of its parent q.push({ temp->left, 1 }); } if (temp->right) { // boolean value is false // here because it is // right child of its parent q.push({ temp->right, 0 }); } } return sum; } // Driver Code int main() { Node* root = new Node(20); root->left = new Node(9); root->right = new Node(49); root->right->left = new Node(23); root->right->right = new Node(52); root->right->right->left = new Node(50); root->left->left = new Node(5); root->left->right = new Node(12); root->left->right->right = new Node(12); cout << "Sum of left leaves is " << sumOfLeftLeaves(root) << endl; return 0; } |
JAVA
// Java program to find sum of all left leaves import java.util.*; class GFG { // A binary tree node static class Node { int key; Node left, right; // constructor to create a new Node Node( int key_) { key = key_; left = null ; right = null ; } }; static class pair { Node first; boolean second; public pair(Node first, boolean second) { this .first = first; this .second = second; } } // Return the sum of left leaf nodes static int sumOfLeftLeaves(Node root) { if (root == null ) return 0 ; // A queue of pairs to do bfs traversal // and keep track if the node is a left // or right child if boolean value // is true then it is a left child. Queue<pair > q = new LinkedList<>(); q.add( new pair( root, false )); int sum = 0 ; // do bfs traversal while (!q.isEmpty()) { Node temp = q.peek().first; boolean is_left_child = q.peek().second; q.remove(); // if temp is a leaf node and // left child of its parent if (is_left_child) sum = sum + temp.key; if (temp.left != null && temp.right != null && is_left_child) sum = sum-temp.key; // if it is not leaf then // push its children nodes // into queue if (temp.left != null ) { // boolean value is true // here because it is left // child of its parent q.add( new pair( temp.left, true )); } if (temp.right != null ) { // boolean value is false // here because it is // right child of its parent q.add( new pair( temp.right, false )); } } return sum; } // Driver Code public static void main(String[] args) { Node root = new Node( 20 ); root.left = new Node( 9 ); root.right = new Node( 49 ); root.right.left = new Node( 23 ); root.right.right = new Node( 52 ); root.right.right.left = new Node( 50 ); root.left.left = new Node( 5 ); root.left.right = new Node( 12 ); root.left.right.right = new Node( 12 ); System.out.print( "Sum of left leaves is " + sumOfLeftLeaves(root) + "" ); } } // This code is contributed by gauravrajput1. |
Python3
# Python3 program to find sum of # all left leaves from collections import deque # A binary tree node class Node: def __init__( self , x): self .key = x self .left = None self .right = None # Return the sum of left leaf nodes def sumOfLeftLeaves(root): if (root = = None ): return 0 # A queue of pairs to do bfs traversal # and keep track if the node is a left # or right child if boolean value # is true then it is a left child. q = deque() q.append([root, 0 ]) sum = 0 # Do bfs traversal while ( len (q) > 0 ): temp = q[ 0 ][ 0 ] is_left_child = q[ 0 ][ 1 ] q.popleft() # If temp is a leaf node and # left child of its parent if ( not temp.left and not temp.right and is_left_child): sum = sum + temp.key # If it is not leaf then # push its children nodes # into queue if (temp.left): # Boolean value is true # here because it is left # child of its parent q.append([temp.left, 1 ]) if (temp.right): # Boolean value is false # here because it is # right child of its parent q.append([temp.right, 0 ]) return sum # Driver Code if __name__ = = '__main__' : root = Node( 20 ) root.left = Node( 9 ) root.right = Node( 49 ) root.right.left = Node( 23 ) root.right.right = Node( 52 ) root.right.right.left = Node( 50 ) root.left.left = Node( 5 ) root.left.right = Node( 12 ) root.left.right.right = Node( 12 ) print ( "Sum of left leaves is" , sumOfLeftLeaves(root)) # This code is contributed by mohit kumar 29 |
C#
// C# program to find sum of all left leaves using System; using System.Collections.Generic; public class GFG { // A binary tree node public class Node { public int key; public Node left, right; // constructor to create a new Node public Node( int key_) { key = key_; left = null ; right = null ; } }; public class pair { public Node first; public bool second; public pair(Node first, bool second) { this .first = first; this .second = second; } } // Return the sum of left leaf nodes static int sumOfLeftLeaves(Node root) { if (root == null ) return 0; // A queue of pairs to do bfs traversal // and keep track if the node is a left // or right child if bool value // is true then it is a left child. Queue<pair> q = new Queue<pair>(); q.Enqueue( new pair(root, false )); int sum = 0; // do bfs traversal while (q.Count != 0) { Node temp = q.Peek().first; bool is_left_child = q.Peek().second; q.Dequeue(); // if temp is a leaf node and // left child of its parent if (is_left_child) sum = sum + temp.key; if (temp.left != null && temp.right != null && is_left_child) sum = sum - temp.key; // if it is not leaf then // push its children nodes // into queue if (temp.left != null ) { // bool value is true // here because it is left // child of its parent q.Enqueue( new pair(temp.left, true )); } if (temp.right != null ) { // bool value is false // here because it is // right child of its parent q.Enqueue( new pair(temp.right, false )); } } return sum; } // Driver Code public static void Main(String[] args) { Node root = new Node(20); root.left = new Node(9); root.right = new Node(49); root.right.left = new Node(23); root.right.right = new Node(52); root.right.right.left = new Node(50); root.left.left = new Node(5); root.left.right = new Node(12); root.left.right.right = new Node(12); Console.Write( "Sum of left leaves is " + sumOfLeftLeaves(root) + "" ); } } // This code is contributed by gauravrajput1 |
Javascript
<script> // JavaScript program to find sum of all left leaves class Node { constructor(key_) { this .left = null ; this .right = null ; this .key = key_; } } // Return the sum of left leaf nodes function sumOfLeftLeaves(root) { if (root == null ) return 0; // A queue of pairs to do bfs traversal // and keep track if the node is a left // or right child if boolean value // is true then it is a left child. let q = []; q.push([root, false ]); let sum = 0; // do bfs traversal while (q.length > 0) { let temp = q[0][0]; let is_left_child = q[0][1]; q.shift(); // if temp is a leaf node and // left child of its parent if (is_left_child) sum = sum + temp.key; if (temp.left != null && temp.right != null && is_left_child) sum = sum-temp.key; // if it is not leaf then // push its children nodes // into queue if (temp.left != null ) { // boolean value is true // here because it is left // child of its parent q.push([temp.left, true ]); } if (temp.right != null ) { // boolean value is false // here because it is // right child of its parent q.push([temp.right, false ]); } } return sum; } let root = new Node(20); root.left = new Node(9); root.right = new Node(49); root.right.left = new Node(23); root.right.right = new Node(52); root.right.right.left = new Node(50); root.left.left = new Node(5); root.left.right = new Node(12); root.left.right.right = new Node(12); document.write( "Sum of left leaves is " + sumOfLeftLeaves(root) + "</br>" ); </script> |
输出
Sum of left leaves is 78
时间复杂性： O（N） 辅助空间： O（N）
本文由 曼尼什语 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
