Leetcode-94-Binary Tree Inorder Traversal

Binary Tree Inorder Traversal

leetcode: https://leetcode.com/problems/binary-tree-inorder-traversal/

Description:

Given the root of a binary tree, return the inorder traversal of its nodes’ values.

Idea:

the order of prerder is left node->parent node->right node(start from the root’s left node)

**Step1: **create the method and use recurision to traverse the whole tree.

**Step2: **move the node to it’s left child and add it’s left child firstly unitl the left subtree finished, then add the parent node, then traverse the right child until the right subtree finished.

Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        //create the result list
        List<Integer> result = new ArrayList<Integer>();
        inorder(root,result);
        return result;
    }

    public void inorder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        //in the inorder, firstly add the left child and start from the root's left child. 
        inorder(root.left, result);
        //now root has move to the left child, add the value of root
        result.add(root.val);
        //then visit the right child of tree.
        inorder(root.right, result);
    }
}