二叉树遍历

前序

顺序为根左右

递归

public static void preLoop(TreeNode root) {
    System.out.println(root.value);
    if (root.left != null) {
        preLoop(root.left);
    }
    if (root.right != null) {
        preLoop(root.right);
    }
}

其他

使用栈，以根右左的顺序进栈，再打印出栈

public static void stackPreLoop(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    TreeNode tmp;
    while (!stack.isEmpty()) {
        tmp = stack.pop();
        System.out.println(tmp.value);
        // 根右左的顺序进栈
        if (tmp.right != null) {
            stack.push(tmp.right);
        }
        if (tmp.left != null) {
            stack.push(tmp.left);
        }
    }
}

中序

左根右

递归

public static void midLoop(TreeNode root) {
    if (root.left != null) {
        midLoop(root.left);
    }
    System.out.println(root.value);
    if (root.right != null) {
        midLoop(root.right);
    }
}

其他

思路就是，先把头结点的所有左边子树压入栈，弹出来的时候，再把右边子树压进去，

如果左右都没有再压入中间

弹出打印

public static void midLoop2(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    while (!stack.isEmpty() || root != null) {
        if (root != null) {
            // 所有左树压入
            stack.push(root);
            // root.left可以为空，下个循环就会剔除
            root = root.left;
        } else {
            // 当左树没了
            root = stack.pop();
            System.out.println(root.value);
            // 指向右节点
            root = root.right;
        }
    }
}

后序

左右根

递归

public static void behindLoop(TreeNode root) {
    if (root.left != null) {
        behindLoop(root.left);
    }
    if (root.right != null) {
        behindLoop(root.right);
    }
    System.out.println(root.value);
}

其他

使用栈存储，先压左再压右

再用一个辅助存储栈，然后出栈打印

public static void stackBehindLoop(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    Stack<TreeNode> helpStack = new Stack<>();
    stack.push(root);
    TreeNode tmp;
    while (!stack.isEmpty()) {
        tmp = stack.pop();
        helpStack.push(tmp);
        // 先压左再压右边
        if (tmp.left != null) {
            stack.push(tmp.left);
        }
        if (tmp.right != null) {
            stack.push(tmp.right);
        }
    }
    while (!helpStack.isEmpty()) {
        tmp = helpStack.pop();
        System.out.println(tmp.value);
    }
}

深度优先遍历

即前序遍历

求最小深度

设叶子节点的深度值为1，先递归到叶子节点，然后往上返回，当有left或者right的节点时，则深度值+1

public static int depth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    if(root.left == null && root.right == null) {
        return 1;
    }
    if (root.left != null && root.right != null) {
        return Math.min(depth(root.left) + 1, depth(root.right) + 1);
    }
    if (root.left != null) {
        return depth(root.left) + 1;
    }
    if (root.right != null) {
        return depth(root.right) + 1;
    }
    return 0;
}

广度优先遍历

求最大宽度

广度优先求最大宽度需要一个辅助队列，把头节点放入队列，然后头节点出队，左节点入队，右节点入队，通过这样的形式可以顺序遍历整棵树。同时还需要一个哈希表，在入队的时候去存储每个节点对应的层数，这样在出队的时候可以结算同层的数目

public static int width(TreeNode root) {
    // 记录节点和层次的关系
    HashMap<TreeNode, Integer> levelMap = new HashMap<>();
    // 通过队列进行顺序遍历
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    levelMap.put(root, 1);
    int currentLevel = 1;
    int currentLevelCount = 0;
    int maxWidth = 0;
    while (!queue.isEmpty()) {
        root = queue.poll();
        if (levelMap.get(root) == currentLevel) {
            currentLevelCount ++;
        } else {
            currentLevel ++;
            // 到达下一层结算
            maxWidth = Math.max(maxWidth, currentLevelCount);
            currentLevelCount = 1;
        }
        if (root.left != null) {
            queue.offer(root.left);
            levelMap.put(root.left, currentLevel+1);
        }
        if (root.right != null) {
            queue.offer(root.right);
            levelMap.put(root.right, currentLevel+1);
        }
        // 这里需要在队列为空的时候求一下最大值，否则就不会记录了
        if (queue.isEmpty()) {
            maxWidth = Math.max(maxWidth, currentLevelCount);
        }
    }
    System.out.println(maxWidth);
    return maxWidth;
}