SHARE
TWEET

in order rec and iter

a guest Oct 21st, 2019 59 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 List<Integer> inorderTraversal(TreeNode root) {
  12.         //stack to traverse the tree
  13.         Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
  14.         //list to hold the inorder traversal
  15.         List<Integer> list = new LinkedList<Integer>();
  16.         // if (root != null){
  17.         //  recInorder(list, root);  
  18.         // }
  19.        
  20.         //traversal temp var
  21.         TreeNode curr = root;
  22.         //while loop to fill out the list
  23.         while (curr != null || !stack.isEmpty()){
  24.             //first push to the stack all of the root's left nodes until theres a null
  25.             while(curr != null){
  26.                 stack.push(curr);
  27.                 curr = curr.left;
  28.             }
  29.            
  30.             //once you've hit the bottom of the left subtree, get the last
  31.             //one that was put it
  32.             if (!stack.isEmpty()){
  33.                 curr = stack.pop();
  34.             }
  35.             //and put it in the list
  36.             list.add(curr.val);
  37.             //then shift over to that node's right subtree and begin the process of going
  38.             //down the left subtree again (if there are any right/left subtrees)
  39.             //tho the if not nulls in the whiles deal with this
  40.             curr = curr.right;
  41.         }
  42.        
  43.         return list;
  44.     }
  45.    
  46.     public void recInorder(List<Integer> list, TreeNode root){
  47.         if (root.left != null){
  48.             recInorder(list, root.left);
  49.         }
  50.         list.add(root.val);
  51.         if (root.right != null){
  52.             recInorder(list, root.right);
  53.         }
  54.     }
  55. }
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