# 94.Binary Tree Inorder Traversal

###### tags: `cycle06_Stack_Queue_Tree`,leetcode`,`easy`

**Binary Tree Inorder Traversal**

>ref: https://leetcode.com/problems/binary-tree-inorder-traversal/
>
Given the root of a binary tree, return the inorder traversal of its nodes' values.

>Example 1:
Input: root = [1,null,2,3]
Output: [1,3,2]

>Example 2:
Input: root = []
Output: []

>Example 3:
Input: root = [1]
Output: [1]

>Constraints:
The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

<h3>recursive</h3>

	List<Integer> ans = new LinkedList<Integer>();

	public List<Integer> inorderTraversal(TreeNode root) {
//  inorder 左中右 preorder 中左右  postorder 左右中

		inorder_recursive(root);

		return ans;
	}

	private void inorder_recursive(TreeNode root) {

		if (root == null)
			return;

		if (root.left != null) {
			inorder_recursive(root.left);
		}

		ans.add(root.val);

		if (root.right != null) {
			inorder_recursive(root.right);
		}

	}

<h3>iterative</h3>

use stack to record the root node,
toll the left most node, then add its right child,
trace the right child inorder,

	private void inorder_while(TreeNode root) {

		Stack<TreeNode> st = new Stack<>();

		TreeNode cur = root;
               //get left child node recursively
		while (!st.isEmpty() || cur != null) {
			while (cur != null) {
                            st.add(cur);
                            cur = cur.left;
			}

		        cur = st.pop();
			ans.add(cur.val);
            
			cur = cur.right;
          

		}

	}

### morris traversal

time O(n)
space O(1)

class Solution {
    public int sumNumbers(TreeNode root) {

        // try morris traversal
        // time O(3n)
        // space O(1)

        TreeNode prev;
        int sum=0;

        int cur=0;


        while(root!=null){

            // check the right most node of left child
            // if null -> right most node's right= root
            // if not null and equal to root, the left part of root are traversal done, go root.right

            if(root.left!=null){
                //find left node right most
                
                prev=root.left;
                int step=1;
                while(prev.right!=null && prev.right!=root){
                    prev=prev.right;
                    step++;
                }

                // go right most
                //if null->first visit,build link to root,go root.left
                if(prev.right==null){
                    //acc
                    cur=cur*10+root.val;
                    prev.right=root;
                    root=root.left;
                }else{
                //if root-> second visit, break and go root.right
                    if(prev.left==null){
                        sum+=cur;
                    }
                    
                    while(step-->0){
                        //go back to root and roll back cur
                        cur/=10;
                    }
                    prev.right=null;
                    root=root.right;
                }
            }else{

                //left empty,
                cur=cur*10+root.val;

                if(root.right==null){
                    sum+=cur;
                }

                // right will go root
                root=root.right;

            }

        }

        return sum;


        
    }
}