BFSは二叉木の階層遍歴を実現し,修正したBFSは二叉木をZigZag遍歴する(LeetCode原題)

深度優先サーチアルゴリズム
実はBFSは私たちの学部でデータ構造を勉強した時に学んだことがありますが、多くの人が私のように当初コードを実現しなかったと思います.ただその原理を知っています.BFSの原理は,2回の染色により,現在の遍歴層のノードをマーキングし,次の遍歴層のノードをマーキングし,この方法を再帰的に実行することである.通常、プログラミングテーマでは、可能なすべての結果を出力する必要があります.DFSを使用しますが、最短パスの結果を得るには、BFSをよく使用します.BFSには様々な実装方法がありますが、以下では2つのキューを使用して実装します.
階層ツリー
まずは木の構造

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int val){
        this.val = val;
    }
}

次に、サンプルツリーを作成し、BFSアルゴリズムを実行します.

public static void main(String[] args) {
        TreeNode node = new TreeNode(0);
        node.left = new TreeNode(1);
        node.right = new TreeNode(2);
        node.left.left = new TreeNode(3);
        node.left.right = new TreeNode(4);
        node.right.right = new TreeNode(5);
        System.out.print(level(node));
    }

具体的なアルゴリズム:

static List> level(TreeNode node){
        List> res = new ArrayList<>();
        Queue queue = new LinkedList<>();
        Queue queue2 = new LinkedList<>();
        if(node!=null) queue.add(node);
        while(!queue.isEmpty()||!queue2.isEmpty()){
            List cur = new ArrayList<>();
            while(!queue.isEmpty()){
                TreeNode tmp = queue.poll();
                cur.add(tmp.val);
                if(tmp.left!=null){
                    queue2.add(tmp.left);
                }
                if(tmp.right!=null){
                    queue2.add(tmp.right);
                }
            }
            while(!queue2.isEmpty()){
                queue.add(queue2.poll());
            }
            res.add(cur);

        }
        return res;
    }

ここでは、現在の遍歴レイヤのノードを格納する2つのキューが使用され、次に遍歴が必要なレイヤのノードを格納する2つのキューが使用されます.
Follow upテーマ:ZigZagのシーケンスレベルでツリーを巡る
タイトルリンク:https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/この問題は私たちが依然として二叉樹を階層的に巡ることを要求しているが、蛇の形の順序にすぎない.ここでは,異なる染色を格納するデータ構造を変更するだけで,キューを2つのスタックに変更し,1回は左サブツリーに,次は右サブツリーに,蛇形の順序を完了することができる.コードは次のとおりです.

public static List> ZigZagLevelTree(TreeNode root){
        List> res = new ArrayList<>();
        Stack q = new Stack<>();
        Stack s = new Stack<>();
        if(root!=null) s.add(root);
        while(!s.isEmpty()||!q.isEmpty()){
            List cur = new ArrayList<>();
            while(!s.isEmpty()){
                TreeNode tmp = s.pop();
                cur.add(tmp.val);
                if(tmp.left!=null) q.push(tmp.left);
                if(tmp.right!=null) q.push(tmp.right);
            }
            if(!cur.isEmpty()) res.add(cur);
            cur = new ArrayList<>();
            while(!q.isEmpty()){
                TreeNode tmp = q.pop();
                cur.add(tmp.val);
                if(tmp.right!=null) s.push(tmp.right);
                if(tmp.left!=null) s.push(tmp.left);
            }
            if(!cur.isEmpty()) res.add(cur);
        }
        return res;
    }