二叉树

遍历

• 广度优先遍历(Breadth-first order):尽可能先访问距离根最近的节点，也称为层序遍历（就是一层一层的遍历）
• 深度优先遍历(Depth-first order)：对于二叉树，可以进一步分成三种（要深入到叶子节点）

  • pre-order前序遍历，对于每一棵子树，先访问该韦点，然后是左子树，最后是右子树

  • in-0rder中序遍历，对于每一棵子树，先访问左子树，然后是该节点，最后是右子树

    • post-ordr后续遍历，对于每一棵子树，先访问左子树，然后是右子树，最后是该节点

递归实现

public class BinaryTree {

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1,
                new TreeNode(2, new TreeNode(4)),
                new TreeNode(3, new TreeNode(5), new TreeNode(6))
        );
        preOrder(treeNode);
        System.out.println();

        midOrder(treeNode);
        System.out.println();

        postOrder(treeNode);
        System.out.println();

    }

    /**
     * 前序遍历
     */
    static void preOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        System.out.println(node.val);
        preOrder(node.left);
        preOrder(node.right);
    }

    /**
     * 中序遍历
     */
    static void midOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        midOrder(node.left);
        System.out.println(node.val);
        midOrder(node.right);
    }

    /**
     * 后续遍历
     */
    static void postOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.val);

    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

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

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

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

        @Override
        public String toString() {
            return "TreeNode{" +
                    "val=" + val +
                    '}';
        }
    }
}

循环遍历

import java.util.LinkedList;

public class BinaryTree {

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1,
                new TreeNode(2, new TreeNode(4)),
                new TreeNode(3, new TreeNode(5), new TreeNode(6))
        );
        postOrder(treeNode);
        System.out.println();

    }

    /**
     * 前序遍历
     */
    static void preOrder(TreeNode node) {
        LinkedList<TreeNode> pop = new LinkedList<>();

        while (node != null || !pop.isEmpty()) {
            if (node != null) {
                //这里打印就是前序遍历
                System.out.println(node.val);
                pop.push(node);
                node = node.left;
            } else {
                node = pop.pop().right;
                //这里打印就是总序遍历
//                if (node != null) {
//                    System.out.println(node.val);
//                }
            }
        }
    }

    /**
     * 中序遍历
     */
    static void midOrder(TreeNode node) {
        LinkedList<TreeNode> pop = new LinkedList<>();

        while (node != null || !pop.isEmpty()) {
            if (node != null) {
                pop.push(node);
                node = node.left;
            } else {
                TreeNode pop1 = pop.pop();
                System.out.println(pop1.val);
                node = pop1.right;
            }
        }
    }

    /**
     * 后续遍历
     */
    static void postOrder(TreeNode node) {
        LinkedList<TreeNode> pop = new LinkedList<>();

        //最近一次的弹栈
        TreeNode lately = null;
        while (node != null || !pop.isEmpty()) {
            if (node != null) {
                pop.push(node);
                node = node.left;
            } else {
                TreeNode pop1 = pop.peek();
                if (pop1.right == null || pop1.right == lately) {
                    //等于null 右子树处理完成
                    TreeNode pop2 = pop.pop();
                    lately = pop2;
                    System.out.println(pop2.val);
                } else {
                    node = pop1.right;
                }
            }
        }
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

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

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

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

        @Override
        public String toString() {
            return "TreeNode{" +
                    "val=" + val +
                    '}';
        }
    }
}

最大深度

public static Integer maxDep(TreeNode node) {
    if (node == null) {
        return 0;
    }
    if (node.left == null && node.right == null) {
        return 1;
    }
    return Integer.max(maxDep(node.left), maxDep(node.right)) + 1;
}

反转

public static TreeNode invertTree(TreeNode node) {
    fn(node);
    return node;
}

public static void fn(TreeNode node) {
    if (node == null) {
        return;
    }
    TreeNode cur = node.left;
    node.left = node.right;
    node.right = cur;
    fn(node.left);
    fn(node.right);
}