前の順序、中の順序、後の順序、段階を熟知してアルゴリズムを遍歴します.

4703 ワード

前の順序を巡回する

①      
public static List res = new ArrayList<>();

public static List binaryTreePreOrderByRecursion(TreeNode treeNode) {

    if (treeNode == null) {
        return res;
    }
    preOrder(treeNode);

    return res;
}

public static void preOrder(TreeNode node) {

    if (node == null) {
        return;
    }
    res.add(node.val);

    preOrder(node.left);
    preOrder(node.right);
}

②       
public static List binaryTreePreOrderByStack(TreeNode treeNode) {
    List res = new ArrayList<>();
    Stack stack = new Stack<>();
    if (treeNode == null) {
        return res;
    }
    stack.push(treeNode);

    while (!stack.isEmpty()) {
        TreeNode cur = stack.pop();
        res.add(cur.val);

        if (cur.right != null) {
            stack.push(cur.right);
        }

        if (cur.left != null) {
            stack.push(cur.left);
        }
    }
    return res;
}

センターフォワード

①  
public static List resInOrder = new ArrayList<>();

public static List binaryTreeInOrderByRecursion(TreeNode node){

    if (node == null){
        return resInOrder;
    }

    processInorder(node);

    return resInOrder;
}

public static void processInorder(TreeNode node){
    if (node == null){
        return;
    }

    processInorder(node.left);
    resInOrder.add(node.val);
    processInorder(node.right);
}

②   
public static List binaryTreeInOrderByUnRecursion(TreeNode node) {

    List res = new ArrayList<>();
    
    Stack stack = new Stack<>();
    
    if (node == null) {
        return res;
    }
    
    //         
    while (node != null) {
        stack.push(node);
        node = node.left;
    }
    
    while (!stack.isEmpty()) {
    
        // + 
        TreeNode cur = stack.pop();
        res.add(cur.val);
    
        //   
        if (cur.right != null){
            cur = cur.right;
    
            //        ，      
            while (cur != null){
                stack.push(cur);
                cur = cur.left;
            }
        }
    }
    return res;
}

巡回

  
static List resPost = new ArrayList<>();

public static List binaryTreePostOrderByRecursion(TreeNode node) {

    if (node == null) {
        return resPost;
    }
    processPost(node);
    return resPost;
}

public static void processPost(TreeNode node) {

    if (node == null) {
        return;
    }
    processPost(node.left);
    processPost(node.right);
    resPost.add(node.val);
}

   
public static List binaryTreePostOrderByUnRecursion(TreeNode node) {

    Stack stack = new Stack<>();
    List res = new ArrayList<>();

    if (node == null) {
        return res;
    }
    //   
    stack.push(node);
    //    
    while (!stack.isEmpty()) {
        TreeNode cur = stack.pop();
        res.add(cur.val);
        if (cur.left != null) {
            //     
            stack.push(cur.left);
        }
        if (cur.right != null) {
            //     
            stack.push(cur.right);
        }
    }
    //   ，    
    Collections.reverse(res);
    return res;

}

巡回
Que行列

offer()添加要素

pollは、最初の要素を返し、

をキューから削除する.

peek()は第一の要素を返し、

を削除しない.

add()とremove()、element()の方法は失敗した時に異常を投げます.
リストor配列

public ArrayList PrintFromTopToBottom(TreeNode root) {
        
        ArrayList result = new ArrayList();
        
        if(root == null){
            return result;
        }
        ArrayList treeNode = new ArrayList();
        treeNode.add(root);
        
        for(int i=0; i

キュー

import java.util.*;

public ArrayList PrintFromTopToBottom(TreeNode root) {
    
    ArrayList result = new ArrayList();
    
    if(root == null){
        return result;
    }
    Queue queue = new LinkedList<>();
    queue.offer(root);
    
    while(!queue.isEmpty()){
        TreeNode node = queue.poll();
        result.add(node.val);   

         if(node.left!=null){
            queue.offer(node.left);
        }
        
         if(node.right!=null){
            queue.offer(node.right);
        }
    }
    return result;
}

(七)行列の中の共通数を探すアルゴリズム

Spring IOCはJSR 330標準注釈を使用しています.