Leetcode-144-Binary Tree Preorder Traversal

Binary Tree Preorder Traversal

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

Description:

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

Idea:

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

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

**Step2: **add parent node firstly, then move the parent node to it’s left child,then in the recurison, when left subtree finished, make the node move to the right child and traverse the right substree.

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> preorderTraversal(TreeNode root) {
        //create the result list
        List<Integer> result = new ArrayList<Integer>();
        preorder(root,result);
        return result;
    }
    public void preorder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        //in the preorder, firstly add the parent node from the root.
        result.add(root.val);
        //then add the left child secondly, at the same time, in the recurision, we move the root to it's left child
        preorder(root.left, result);
        //then add the right child thirdly, at the same time, in the recurision, we move the root to it's left child
        preorder(root.right, result);
    }
}