• API
• FAQ
• Tools
• Archive
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
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.         }