打遍天下二叉樹

ps: 文中的所有代碼均可在 https://github.com/xfhy/Algorithms 中找到. 該專案有一些關于二叉樹的基本學習代碼和二叉樹的題解等.

1. 基本概念

• 二叉樹（binary tree） 是樹的一種特殊形式，二叉，顧名思義，這種樹的每個節點最多有2個孩子節點，注意，這里是最多有2個，也可能只有1個，或者沒有孩子節點，
• 滿二叉樹: 一個二叉樹的所有非葉子節點都存在左右孩子,并且所有葉子節點都在同一層級上.
• 完全二叉樹: 對一個有n個節點的二叉樹,按層級順序編號,則所有節點的編號為從1到n.如果這個樹所有節點和同樣深度的滿二叉樹的編號為從1到n的節點位置相同,則這個二叉樹為完全二叉樹.
• 二叉查找樹(又名: 二叉排序樹,二叉搜索樹): 這種二叉樹的主要作用就是進行查找操作.它的中序遍歷是排好序了的,即由小到大. 滿足二叉查找樹需要幾個條件
  1. 如果左子樹不為空,則左子樹上所有節點的值均小于根節點的值
  2. 如果右子樹不為空,則右子樹上所有節點的值均大于根節點的值
  3. 左右子樹也都是二叉查找樹
• 從節點之間位置關系的角度來看，二叉樹的遍歷分為4種
  1. 前序遍歷(根節點在前)
  2. 中序遍歷
  3. 后序遍歷
  4. 層序遍歷
• 從更宏觀的角度來看,二叉樹的遍歷歸結為兩大類
  1. 深度優先遍歷(前序、中序、后序遍歷)
  2. 廣度優先遍歷(層序遍歷)

文中的二叉樹節點定義如下:

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

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

2. 深度優先遍歷

2.1 遞回方式

遞回的方式實作深度優先遍歷代碼非常簡潔,往往只需要幾行代碼即可.用遞回來實作深度優先遍歷是比較自然的,僅僅只是輸出的執行位置不同而已.下面我們來看哈代碼:

//前序遍歷
public void preOrderTraveral(TreeNode node) {
    if (node == null) {
        return;
    }
    System.out.println(node.val);
    preOrderTraveral(node.left);
    preOrderTraveral(node.right);
}

//中序遍歷
public void inOrderTraveral(TreeNode node) {
    if (node == null) {
        return;
    }
    inOrderTraveral(node.left);
    System.out.println(node.val);
    inOrderTraveral(node.right);
}

//后序遍歷
public void postOrderTraveral(TreeNode node) {
    if (node == null) {
        return;
    }
    postOrderTraveral(node.left);
    postOrderTraveral(node.right);
    System.out.println(node.val);
}

2.2 非遞回方式

絕大多數可以用遞回解決的問題,都可以用堆疊來解決.它們都有回溯的特性.

首先來看前序遍歷,實作非遞回方式前序遍歷的思路:

1. 用一個堆疊來記錄訪問過的節點
2. 然后從根節點開始往左節點遍歷,一直往下,直到左邊沒有左節點
3. 然后彈堆疊,繼續訪問彈出的這個元素的右節點.如果這個右節點有左子樹的話,把當前節點當做根節點,繼續重復2步驟
4. 直到把所有元素都遍歷完成

//前序遍歷 
public void preOrderTraveralWithStack(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode treeNode = root;
    while (treeNode != null || !stack.isEmpty()) {
        //不斷往堆疊中壓入左節點,直到左邊沒有左節點
        while (treeNode != null) {
            System.out.println(treeNode.val);
            stack.push(treeNode);
            treeNode = treeNode.left;
        }
        //彈堆疊 訪問右邊節點
        if (!stack.isEmpty()) {
            treeNode = stack.pop();
            treeNode = treeNode.right;
        }
    }
}

然后我們來看中序遍歷,在前序遍歷的基礎上,只需要稍等改動一下sout的位置即可.從根節點開始找二叉樹的最左節點,找到最左節點后訪問,對于每個節點來說,它都是以自己為根的子樹的根節點,訪問完之后就可以轉到右兒子上了.

public void middleOrderTraversal(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode treeNode = root;
    while (treeNode != null || !stack.isEmpty()) {
        //不斷往堆疊中壓入左節點,直到左邊沒有左節點
        while (treeNode != null) {
            stack.push(treeNode);
            treeNode = treeNode.left;
        }
        //彈堆疊 訪問右邊節點
        if (!stack.isEmpty()) {
            treeNode = stack.pop();
            System.out.println(treeNode.val);
            treeNode = treeNode.right;
        }
    }
}

后續遍歷就稍微復雜點,其實也只需要在先序遍歷的基礎上稍微改改就行了,先序是:中前后,改一下while中的左右壓堆疊順序就是: 中后前,得到資料之后再反轉,即:前后中.就得到了最后的結果

public List<Integer> postOrderTraversal(TreeNode root) {
    LinkedList<Integer> res = new LinkedList<>();
    if (root == null) {
        return res;
    }
    LinkedList<TreeNode> stack = new LinkedList<>();
    stack.add(root);
    while (!stack.isEmpty()) {
        TreeNode pop = stack.pop();
        res.add(pop.val);
        if (pop.left != null) {
            stack.push(pop.left);
        }
        if (pop.right != null) {
            stack.push(pop.right);
        }
    }
    Collections.reverse(res);
    return res;
}

3. 廣度優先遍歷

即按照高度順序一層一層的訪問整棵樹,高層次節點將會比低層次節點先被訪問到.

下面來看一下用代碼怎么實作二叉樹的層序遍歷,這里需要用到一個佇列.將根節點入隊,

/**
 * 二叉樹層序遍歷
 */
public void levelOrderTraversal(TreeNode root) {
    //1. 宣告一個佇列,將根節點入隊
    //2. 然后將根節點出隊,在根節點出隊時將根節點的左節點和右節點都入隊
    //3. 回圈遍歷佇列,依次出隊,在第2步中的左節點出隊時,將自己視為根節點,然后將左右節點入隊. 同理,右節點也一樣
    //4. 遍歷完佇列時,所有節點的左右節點都遍歷完了.
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.println(node.val);
        if (node.left != null) {
            queue.offer(node.left);
        }
        if (node.right != null) {
            queue.offer(node.right);
        }
    }
}

4. 案例

4.1 二叉樹的最大深度

根節點的最大深度=左節點最大深度+右節點最大深度+1

這就非常適合遞回,直接遞回安排.

/**
 * 二叉樹的最大深度
 * 思路: 比較左子樹的最大深度和右子樹的最大深度,
 * 左子樹的最大深度同樣也適用于這種思路,右子樹的最大深度同樣也適用于這種思路
 * 這就很適合遞回,在訪問到空節點時退出.
 * 最后深度需要+1,因為需要計算上根節點.
 */
public static int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

4.2 記錄每一層的所有元素

有時候我們需要記錄每一層上的所有元素,這時我們可以在上面二叉樹層序遍歷的基礎上,稍稍改進一下即可: 遍歷一層的時候,先記錄這層的元素個數,再依次添加到記錄的集合中,順便把這些元素的左右節點入隊. 繼續遍歷下一層.

/**
 * 二叉樹層序遍歷 且記錄每一層的所有元素
 *
 * @param root 二叉樹根節點
 */
public List<List<TreeNode>> levelOrderTraversals(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    List<List<TreeNode>> tree = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        LinkedList<TreeNode> levels = new LinkedList<>();
        for (int i = 0; i < size; i++) {
            TreeNode poll = queue.poll();
            levels.add(poll);
            if (poll.left != null) {
                queue.offer(poll.left);
            }
            if (poll.right != null) {
                queue.offer(poll.right);
            }
        }
        tree.add(levels);
    }
    return tree;
}