数据结构-二叉树的遍历

二叉树的遍历广义上是指下面我们说的七种遍历

深度优先搜索 : 递归完成 前序 中序 后序 的遍历
广度优先搜索 : 层序遍历(借助队列)
非递归的迭代法完成前中后遍历(借助栈)

代码合集如下

package TreeDemo;
import java.util.*;
public class BinaryTreeTest {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

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

    /**
     * 下面的几种方法分别是
     * 前中后序的递归遍历(又称深度优先搜索)
     * 前中后序的迭代法遍历(用栈去模拟)
     * 层序遍历(广度优先搜索 --> 用队列模拟)
     */

    //前序遍历的递归法
    List<Integer> list1 = new ArrayList<>();

    public List<Integer> preOrder(TreeNode root) {
        if (root == null) {
            return list1;
        }

        //进入递归环节
        list1.add(root.val);
        preOrder(root.left);
        preOrder(root.right);
        return list1;
    }

    //前序遍历的非递归写法(迭代法)
    private Stack<TreeNode> stack1 = new Stack<>();
    private List<Integer> list2 = new ArrayList<>();

    public List<Integer> preOrderUseWhile(TreeNode root) {
        if (root == null) {
            return list2;
        }

        stack1.push(root);
        while (!stack1.isEmpty()) {
            TreeNode node = stack1.pop();
            list2.add(node.val);
            if (node.right != null) {
                stack1.push(root.right);
            }
            if (node.left != null) {
                stack1.push(root.left);
            }
        }
        return list2;
    }


    //中序遍历的递归法
    private List<Integer> list3 = new ArrayList<>();

    public List<Integer> inOrder(TreeNode root) {
        if (root == null) {
            return list3;
        }

        inOrder(root.left);
        list3.add(root.val);
        inOrder(root.right);
        return list3;
    }


    //中序遍历的迭代法
    private List<Integer> list4 = new ArrayList<>();
    private Stack<TreeNode> stack2 = new Stack<>();

    public List<Integer> inOrderUseWhile(TreeNode root) {
        if (root == null) {
            return list4;
        }

        TreeNode cur = root;
        //这里的逻辑判断要重视一下啊,这个条件的逆命题是栈为空同时指针也为空...
        while (!stack2.isEmpty() || cur != null) {
            if (cur != null) {
                stack2.push(cur);
                cur = cur.left;
            } else {
                TreeNode node = stack2.pop();
                list4.add(node.val);
                cur = node.right;
            }
        }
        return list4;
    }


    //后序遍历的递归法
    private List<Integer> posOrderList = new ArrayList<>();

    public List<Integer> posOrder(TreeNode root) {
        if (root == null) {
            return posOrderList;
        }

        posOrder(root.left);
        posOrder(root.right);
        posOrderList.add(root.val);
        return posOrderList;
    }


    //后续遍历的迭代法
    private List<Integer> posOrderlist = new ArrayList<>();
    private Stack<TreeNode> posOrderStack = new Stack<>();

    public List<Integer> posOrderUseWhile(TreeNode root) {
        if (root == null) {
            return posOrderlist;
        }

        posOrderStack.push(root);
        while (!posOrderStack.isEmpty()) {
            TreeNode node = posOrderStack.pop();
            posOrderlist.add(node.val);
            if (node.left != null) {
                posOrderStack.push(node.left);
            }
            if (node.right != null) {
                posOrderStack.push(node.right);
            }
        }

        //反转顺序表
        int size = posOrderlist.size();
        int left = 0;
        int right = size - 1;
        while (left <= right) {
            Integer temp = posOrderlist.get(left);
            posOrderlist.set(left, posOrderlist.get(right));
            posOrderlist.set(right, temp);
            left++;
            right--;
        }
        return posOrderlist;
    }


    /**
     * 二叉树的层序遍历,运用的是队列的思想
     * 核心逻辑就是利用队列的大小来定向的控制移动元素的数量从而达到层序遍历的效果
     * 也就是我们图论中的广度优先搜索...
     */
    public List<List<Integer>> levelList = new ArrayList<>();
    public Queue<TreeNode> queue = new LinkedList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null){
            return levelList;
        }

        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> tempList = new ArrayList<>();
            while(size-- != 0){
                TreeNode node = queue.poll();
                tempList.add(node.val);
                if(node.left != null){
                    queue.offer(node.left);
                }
                if(node.right != null){
                    queue.offer(node.right);
                }
            }
            levelList.add(tempList);
        }
        return levelList;
    }
}

层序遍历的应用 --> 补档"前世今生"

/**
 * 今天我们正式用树的观点解决一下前世今生
 */
class PreLiveAndCur {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode() {

        }

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


    /**
     * 这个方法的作用是用递归尝试生成一颗满二叉树
     * @param level : 层数
     * @return
     */
    public static TreeNode getFullTree(int level) {
        if (level == 1) {
            return new TreeNode(2);
        }

        TreeNode root = new TreeNode(2);
        root.left = getFullTree(level - 1);
        root.right = getFullTree(level - 1);
        return root;
    }


    /**
     * 不用计数的方式,利用我们的层序迭代遍历来初始化(广度优先搜索)
     * 由于我们这玩意百分百是一个满二叉树,也就是我们的size一定为2的倍数
     * @param root
     * @param level
     */
    private static Queue<TreeNode> queue = new LinkedList<>();

    public static void initLevelValue(TreeNode root, int level) {
        if(root == null){
            throw new RuntimeException("不是哥们...");
        }
        int countMax = (int) Math.pow(2, level - 1);
        queue.offer(root);
        boolean flag = false;
        int value = 1;
        while(!queue.isEmpty()){
            int size = queue.size();
            if(size == countMax){
                flag = true;
            }
            while(size-- != 0){
                TreeNode node = queue.poll();
                if(flag){
                    node.val = value++;
                }
                if(node.left != null){
                    queue.offer(node.left);
                }
                if(node.right != null){
                    queue.offer(node.right);
                }
            }
        }
    }

    /**
     * 根据传入的根节点与字符串(注意传入的两个参数要进行匹配)
     * @param s : 字符串
     * @param root : 根节点的坐标
     * @return
     */
    public static int getContext(String s,TreeNode root){
        TreeNode cur = root;
        for(int i = 0; i < s.length(); ++i){
            char tempChar = s.charAt(i);
            if(tempChar == 'y'){
                cur = cur.left;
            }else{
                cur = cur.right;
            }
        }
        return cur.val;
    }

    //创建一个集合类链表来接收返回数据
    private static List<Integer> res = new LinkedList<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int problemNumber = sc.nextInt();
        int personNumber = sc.nextInt();
        int level = problemNumber + 1;
        TreeNode root = getFullTree(level);
        initLevelValue(root,level);
        for(int i = 0; i < personNumber; ++i){
            String s = sc.next();
            res.add(getContext(s,root));
        }
        for(Integer elem : res){
            System.out.println(elem);
        }
    }
}