Created
September 30, 2016 04:13
-
-
Save audreylee25128/cf604f5596b06c6c9109f847165632f2 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // Audrey Lee (UNI al3626) Solution | |
| // To be run with TreeNode.java in the same directory | |
| // Precondition: There is a Binary tree | |
| // Postcondition: Depth of the Binary tree | |
| public class Solution { | |
| public static int maxDepth(TreeNode root) { | |
| // Base case: if tree is empty | |
| if (root== null || (root.getRight() == null && root.getLeft() == null)) return 0; | |
| int lDepth, rDepth; | |
| // Depth of the left subtree | |
| lDepth= maxDepth(root.getLeft()); | |
| // Depth of the right subtree | |
| rDepth= maxDepth(root.getRight()); | |
| return Math.max(lDepth, rDepth) + 1; | |
| } | |
| /********************For Testing Purposes*********************************/ | |
| /* | |
| public static void main(String[] args){ | |
| //System.out.println("Testing"); | |
| TreeNode root= new TreeNode(0,null,null); | |
| root.setLeft(new TreeNode(1,null,null)); | |
| root.getLeft().setRight(new TreeNode(1, null, null)); | |
| // Height of left subtree should be 2 | |
| root.setRight(new TreeNode(2, null, null)); | |
| root.getRight().setRight(new TreeNode(2,null,null)); | |
| root.getRight().getRight().setRight(new TreeNode(2,null,null)); | |
| root.getRight().getRight().getRight().setLeft(new TreeNode(2,null,null)); | |
| // Height of right subtree should be 4 | |
| System.out.println(maxDepth(root)); // 4 | |
| } | |
| */ | |
| } | |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // Audrey Lee (UNI: al3626) Solution | |
| /**************************************************************************** | |
| This is a TreeNode class that I made to help with testing out my solution. | |
| *****************************************************************************/ | |
| //Definition for a binary tree node. | |
| public class TreeNode { | |
| public int val; | |
| public TreeNode left; | |
| public TreeNode right; | |
| public TreeNode(int x){ | |
| this(x,null,null); | |
| } | |
| public TreeNode(int x, TreeNode l, TreeNode r){ | |
| val = x; | |
| left = l; | |
| right = r; | |
| } | |
| public TreeNode getLeft(){ | |
| return left; | |
| } | |
| public TreeNode getRight(){ | |
| return right; | |
| } | |
| public int getValue(){ | |
| return val; | |
| } | |
| public TreeNode setLeft(TreeNode newLeft){ | |
| TreeNode ans = left; | |
| left = newLeft; | |
| return ans; | |
| } | |
| public TreeNode setRight(TreeNode newRight){ | |
| TreeNode ans = right; | |
| right = newRight; | |
| return ans; | |
| } | |
| public String toString(){ | |
| return getValue() + ""; | |
| } | |
| } | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment