SHARE
TWEET

count all nodes in a bst

a guest Oct 21st, 2019 81 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. class Solution {
  11.     public int countNodes(TreeNode root) {
  12.         // Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
  13.         // int count = 0;
  14.         // TreeNode curr = root;
  15.         // while(curr != null || !stack.isEmpty()){
  16.         //     while(curr != null){
  17.         //         stack.push(curr);
  18.         //         curr = curr.left;
  19.         //     }
  20.         //     count++;
  21.         //     curr = stack.pop();
  22.         //     curr = curr.right;
  23.         // }
  24.         // return count;
  25.        
  26.         /**
  27.         So the bellow implementation teaches you that when youre carrying through an addable
  28.         number you dont need a new method to include it in the signature para pasarlo,
  29.         you can just make it en la funcion y lo seteas a 1 y le sumas a esa variable el
  30.         resultado de la proxima iteracion. base case es cuando sea nulo, return 0;
  31.         this way you dont have to only do half the tree and ending it with a return.
  32.         you can just add all of it to the 'global' variable and return that in the end
  33.         from the first call;
  34.         **/
  35.        
  36.         //current sum (assuming root is not null)
  37.        
  38.     int sum = 1;
  39.     //base case
  40.     if (root == null) return 0;
  41.     //check left
  42.     if (root.left != null) {
  43.         //add left subtree to sum
  44.         sum += countNodes(root.left);
  45.     }
  46.     //check right
  47.     if (root.right != null) {
  48.         //add right subtree to sum
  49.         sum += countNodes(root.right);
  50.     }
  51.     //result
  52.     return sum;
  53.     }
  54. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top