Subject to introduce

Force buckle 144 questions: leetcode-cn.com/problems/bi…

Method one: recursion

The code is as follows:

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if(root == null) {
            return result;
        }
        preorder(root,result);
        return result;
    }

    public void  preorder(TreeNode root,List<Integer> result) {
        if(root == null) {
            return;
        }
        // Iterate over the root node firstresult.add(root.val); preorder(root.left,result); preorder(root.right,result); }}Copy the code

Method 1: iteration

First we need to create a Stack to hold the nodes. First we want to print the data of the root node. At this point the Stack is empty, so we add the head node to the Stack first and print it.

Then we should print the left subtree first, and then the right subtree. So the first thing you add to the Stack is the right subtree, and then the left subtree. Here’s what you get:

The code is as follows:

public static void preOrderIteration(TreeNode head) {
    if (head == null) {
        return;
    }
    Stack<TreeNode> stack = new Stack<>();
    stack.push(head);
    while(! stack.isEmpty()) { TreeNode node = stack.pop(); System.out.print(node.value +"");
        if(node.right ! =null) {
                stack.push(node.right);
        }
        if(node.left ! =null) { stack.push(node.left); }}}Copy the code