本文總結(jié)了關(guān)于二叉樹的常見算法題

判斷葉子節(jié)點：if (root.left == null && root.right == null)

1、遞歸遍歷

每個節(jié)點會到達三次，前序為輸出第一次到達，中序為輸出第二次到達，后序為第三次到達

1.1、遞歸先序

public void preOrderRecur(TreeNode head) {
    if (head == null) {
        return;
    }
    System.out.print(head.val+" ");
    preOrderRecur(head.left);
    preOrderRecur(head.right);
}

1.2、遞歸中序

public void inOrderRecur(TreeNode head) {
    if (head == null) {
        return;
    }
    inOrderRecur(head.left);
    System.out.print(head.val + " ");
    inOrderRecur(head.right);
}

1.3、遞歸后序

public void postOrderRecur(TreeNode head) {
    if (head == null) {
        return;
    }
    postOrderRecur(head.left);
    postOrderRecur(head.right);
    System.out.print(head.val + " ");
}

2、非遞歸遍歷

2.1、非遞歸先序

需要自己用棧記錄，每次取出棧頂cur，如果cur的右孩子不為空，則先放右孩子，如果cur的左孩子不為空，在把左孩子放入棧中。

public void preOrderUnRecur(TreeNode head) {
    if (head == null) {
        return;
    }
    Stack<TreeNode> stack = new Stack<>();
    stack.push(head);
    while (!stack.isEmpty()) {
        TreeNode cur = stack.pop();
        System.out.print(cur.val + " ");
        if (cur.right != null) stack.push(cur.right);
        if (cur.left != null) stack.push(cur.left);
    }
}

2.2、非遞歸中序

如果當(dāng)前節(jié)點不為空，就把當(dāng)前節(jié)點放入棧中，并向左孩子移動；如果當(dāng)前節(jié)點為空，就去取出棧頂?shù)脑?，打印它，并向它的右孩子移動?/p>

public void inOrderUnRecur(TreeNode cur) {
    if (cur == null) {
        return;
    }
    Stack<TreeNode> stack = new Stack<>();

    while (!stack.isEmpty() || cur != null) {
        if (cur != null) {
            stack.push(cur);
            cur = cur.left;
        } else {
            cur = stack.pop();
            System.out.print(cur.val + " ");
            cur = cur.right;
        }
    }
}

2.3、非遞歸后序

? 兩個棧，一個棧用來存放結(jié)果res，一個存放還沒放入res的棧stack。每次從stack棧頂pop取出元素，放入res棧中，同時把pop的左孩子放入stack，右孩子放入stack，當(dāng)然要判斷是否為空。

public void posOrderUnRecur1(TreeNode head) {
    if (head == null) {
        return;
    }
    Stack<TreeNode> stack = new Stack<>();
    Stack<TreeNode> res = new Stack<>();
    stack.push(head);
    while (!stack.isEmpty()) {
        TreeNode pop = stack.pop();
        res.push(pop);
        if (pop.left != null) stack.push(pop.left);
        if (pop.right != null) stack.push(pop.right);
    }
    while (!res.isEmpty()) {
        System.out.print(res.pop().val + " ");
    }
}

3、Morris遍歷

普通的遞歸遍歷 和 非遞歸遍歷的時間復(fù)雜度是O(N)，額外空間復(fù)雜度是O(h)；
二叉樹的Morris遍歷，時間復(fù)雜度O(N)，額外空間復(fù)雜度O(1)?？梢杂脕韮?yōu)化大部分基于遍歷二叉樹的問題。

特點：一個節(jié)點，有左孩子就會訪問兩次，沒有左孩子只會訪問一次

規(guī)則：

? 假設(shè)當(dāng)前節(jié)點是cur，開始時cur指向頭結(jié)點
①. 如果cur沒有左孩子，cur直接向右移動【cur = cur.right】
②. 如果cur有左孩子，找到cur左子樹上最右的節(jié)點【mostRight】
1、如果mostRight的右指針指向空，讓右指針指向cur，然后cur向左移動【cur = cur.left】
2、如果mostRight的右指針指向cur，讓右指針指向null，然后cur向右移動【cur = cur.right】
當(dāng)cur為空時遍歷結(jié)束

public void morrisPure(TreeNode root) {
    if (root == null) {
        return;
    }
    TreeNode cur = root;
    TreeNode mostRight = null;
    while (cur != null) {
        if (cur.left == null) {
            cur = cur.right;//沒有左孩子，第一次訪問【也可以理解為第一次第二次同時】
        } else {
            mostRight = cur.left;
            while (mostRight.right != null && mostRight.right != cur) {
                mostRight = mostRight.right;
            }
            if (mostRight.right == null) {//有左孩子，第一次訪問
                mostRight.right = cur;
                cur = cur.left;
            } else {
                mostRight.right = null;//有左孩子，第二次訪問
                cur = cur.right;
            }
        }
    }
}

3.1、Morris先序

morrisPure中第一次訪問輸出

3.2、Morris中序

morrisPure中第二次訪問輸出

3.3、Morris后序

只關(guān)心能訪問兩次的節(jié)點，也就是有左孩子的節(jié)點，

1、第二次訪問這些節(jié)點時，逆序打印節(jié)點的左子樹，這時就需要反轉(zhuǎn)左子樹，打印，在反轉(zhuǎn)回來
2、遍歷完成后，逆序打印整個樹的右邊界

public void morrisPos(TreeNode root) {
    if (root == null) {
        return;
    }
    TreeNode cur = root;
    TreeNode mostRight = null;
    while (cur != null) {
        if (cur.left == null) {
            cur = cur.right;
        } else {
            mostRight = cur.left;
            while (mostRight.right != null && mostRight.right != cur) {
                mostRight = mostRight.right;
            }
            if (mostRight.right == null) {
                mostRight.right = cur;
                cur = cur.left;
            } else {
                mostRight.right = null;
                reversePrintEdge(cur.left); //有左孩子，第二次訪問，才逆序打印左孩子的右邊界
                cur = cur.right;
            }
        }
    }
    reversePrintEdge(root); //最后逆序打印根節(jié)點的右邊界
    System.out.println();
}

public void reversePrintEdge(TreeNode left) {
    TreeNode tail = reverseEdge(left);
    TreeNode cur = tail;
    while (cur != null) {
        System.out.print(cur.val + " ");
        cur = cur.right;
    }
    reverseEdge(tail);
}

public TreeNode reverseEdge(TreeNode node) {
    TreeNode next = null;
    TreeNode pre = null;
    while (node != null) {
        next = node.right;
        node.right = pre;
        pre = node;
        node = next;
    }
    return pre;
}

4、二叉樹的最大深度

//使用遞歸    
public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left, right) + 1;
    }

//使用廣度優(yōu)先遍歷
public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    int height = 0;
    while (!queue.isEmpty()) {
        int size = queue.size();
        height++;
        for (int i = 0; i < size; i++) {
            TreeNode cur = queue.remove();
            if (cur.left != null) queue.add(cur.left);
            if (cur.right != null) queue.add(cur.right);
        }
    }
    return height;
}

5、二叉樹的最小深度

public int minDepth2(TreeNode root) {
    if (root == null) {
        return 0;
    }
    if (root.left == null && root.right == null) {
        return 1;
    }//判斷葉子節(jié)點

    int left = root.left != null ? minDepth2(root.left) : Integer.MAX_VALUE;
    int right = root.right != null ? minDepth2(root.right) : Integer.MAX_VALUE;

    return Math.min(left, right) + 1;
}

//使用廣度優(yōu)先遍歷
public int minDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    int min = 0;
    while (!queue.isEmpty()) {
        int size = queue.size();
        min++;
        for (int i = 0; i < size; i++) {
            TreeNode cur = queue.remove();
            if (cur.left == null && cur.right == null) {
                return min;
            }//判斷葉子節(jié)點
            if (cur.left != null) queue.add(cur.left);
            if (cur.right != null) queue.add(cur.right);
        }
    }
    return min;
}

6、二叉樹層次遍歷

6.1、普通層次遍歷

二叉樹.png

輸出：1、2、3、4、5、6、7

使用隊列，從對頭取出cur，把cur的左孩子，右孩子，依次放入對尾

public  void levelOrder(TreeNode head) {
    if (head == null) {
        return;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(head);
    while (!queue.isEmpty()) {
        TreeNode cur = queue.remove();
        System.out.print(cur.val + " ");
        
        if (cur.left != null) {
            queue.add(cur.left);
        }
        if (cur.right != null) {
            queue.add(cur.right);
        }
    }
}

7、 二叉樹的鏡像

請完成一個函數(shù)，輸入一個二叉樹，該函數(shù)輸出它的鏡像。

例如輸入：
4
/
2 7
/ \ /
1 3 6 9
鏡像輸出：
4
/
7 2
/ \ /
9 6 3 1

public TreeNode mirrorTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;

    mirrorTree(root.left);
    mirrorTree(root.right);
    return root;
}

8、 判斷是否是對稱的二叉樹

請實現(xiàn)一個函數(shù)，用來判斷一棵二叉樹是不是對稱的。如果一棵二叉樹和它的鏡像一樣，那么它是對稱的。

例如，二叉樹 [1,2,2,3,4,4,3] 是對稱的
1
/
2 2
/ \ /
3 4 4 3
但是下面這個 [1,2,2,null,3,null,3] 則不是鏡像對稱的:
1
/
2 2
\
3 3

//遞歸，也可以用層次遍歷做
public boolean isSymmetric(TreeNode root) {
    if (root == null) {
        return true;
    }
    return isEqual(root.left, root.right);
}

public boolean isEqual(TreeNode left, TreeNode right) {
    if (left == null && right == null) {
        return true;
    }
    if (left == null || right == null) {
        return false;
    }
    if (left.val != right.val) {
        return false;
    }
    return isEqual(left.left, right.right) && isEqual(left.right, right.left);
}

9、 二叉樹中和為某一值的路徑

回溯法：

注意：1、必須要是葉子節(jié)點才添加和滿足條件的列表；2、可能存在負數(shù)

public List<List<Integer>> pathSum(TreeNode root, int sum) {
    if (root == null) {
        return new ArrayList<>();
    }
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();
    traceBack(root, res, temp, 0, sum);
    return res;
}

public void traceBack(TreeNode root, List<List<Integer>> res, List<Integer> temp, int cur, int sum) {
    if (root == null) {
        return;
    }

    temp.add(root.val);

    if (root.left == null && root.right == null) {//必須要是葉子節(jié)點
        if (cur + root.val == sum) {//和要滿足要求
            res.add(new ArrayList<>(temp));
        }
    }

    traceBack(root.left, res, temp, cur + root.val, sum);
    traceBack(root.right, res, temp, cur + root.val, sum);
    temp.remove(temp.size() - 1);
}

10、 重建二叉樹

輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請重建該二叉樹。
假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。

例如，給出
前序遍歷 preorder = [3,9,20,15,7]
中序遍歷 inorder = [9,3,15,20,7]
返回如下的二叉樹：

3
/
9 20
/
15 7

重建二叉樹.png

思路：

1、先序的第一個位置node1是root節(jié)點；
2、在中序中找到node1的位置k，以及計數(shù)count；
3、根據(jù)k和count進一步對先序數(shù)組和中序數(shù)組劃分，如上圖

public TreeNode buildTree(int[] preorder, int[] inorder) {
    if (preorder == null || preorder.length == 0 ||
            inorder == null || inorder.length == 0 ||
            preorder.length != inorder.length) {
        return null;
    }
    return build(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
}

/**
 * @param preI 表示先序的開始位置
 * @param preJ 表示先序的結(jié)束位置
 * @param inI  表示中序的開始位置
 * @param inJ  表示中序的結(jié)束位置
 */
public TreeNode build(int[] preorder, int[] inorder, int preI, int preJ, int inI, int inJ) {
    if (preI > preJ || inI > inJ) {
        return null;
    }
    //前序遍歷的第一個是root
    TreeNode head = new TreeNode(preorder[preI]);

    //在中序中找到前序的頭節(jié)點的位置k，
    int k = inI;
    int count = 0;
    while (inorder[k] != head.val) {
        k++;
        count++;
    }

    //將先序，中序，按照count,和k劃分
    head.left = build(preorder, inorder, preI + 1, preI + count, inI, k - 1);
    head.right = build(preorder, inorder, preI + count + 1, preJ, k + 1, inJ);
    return head;
}

11、序列化反序列化二叉樹

      1      
    /   \    
  2       3  
 /       / \ 
4       5   6

? 序列化：序列化的時候需要將所有的null節(jié)點都序列化進去，并且節(jié)點之間要有分隔，比如null節(jié)點用#表示，例子中的序列化結(jié)果為：1,2,4,#,#,#,3,5,#,#,6,#,#,

? 反序列化：

public String serialize(TreeNode root) {
    if (root == null) {
        return "#,";
    }
    String cur = root.val + ",";
    return cur + serialize(root.left) + serialize(root.right);
}

public TreeNode deserialize(String data) {
    if (data == null || data.length() == 0) {
        return null;
    }
    String[] nodes = data.split(",");
    return buildTree(nodes, new int[]{0});
}

public TreeNode buildTree(String[] nodes, int[] cur) {
    if (cur[0] >= nodes.length) {
        return null;
    }
    String val = nodes[cur[0]++];
    
    if (val.equals("#")) return null;
    TreeNode root = new TreeNode(Integer.parseInt(val));
    
    root.left = buildTree(nodes, cur);
    root.right = buildTree(nodes, cur);
    return root;
}

12、判斷平衡二叉樹

一個平衡二叉樹要求：左子樹是平衡二叉樹、右子樹是平衡二叉樹、而且，左右子樹的高度差不超過1。

public boolean isBalanced(TreeNode root) {
    if (root == null) {
        return true;
    }
    return height(root) >= 0;
}

//height = -1 表示已經(jīng)不平衡了 
public int height(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int left = height(root.left);
    int right = height(root.right);

    if (left == -1 || right == -1 || Math.abs(left - right) > 1) {
        return -1;
    }
    return 1 + Math.max(left, right);
}

13、判斷二叉搜索樹

一個二叉搜索樹：左孩子<父節(jié)點<右孩子 ,BST的中序遍歷的結(jié)果遞增的

思路：在中序遍歷的過程中判斷是否滿足目前節(jié)點的值比前一個節(jié)點的值大，可以使用普通非遞歸遍歷，或者是Moriss遍歷

//普通非遞歸遍歷
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        TreeNode cur = root;
        Integer pre = null;

        Stack<TreeNode> stack = new Stack<>();
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                TreeNode pop = stack.pop();

                if (pre != null && pop.val <= pre) { //這是為了避免第一個節(jié)點出現(xiàn)最小整數(shù)無法判斷
                    return false;
                }
                System.out.println(pop.val);
                pre = pop.val;
                cur = pop.right;
            }
        }
        return true;
    }

//Moriss遍歷
public boolean isValidBST(TreeNode root) {
    if (root == null) {
        return true;
    }
    TreeNode cur = root;
    TreeNode mostRight = null;
    Integer pre = null;
    while (cur != null) {
        if (cur.left == null) {
            if (pre != null && cur.val <= pre) {
                return false;
            }
            pre = cur.val;
            cur = cur.right;//沒有左孩子，第一次訪問【也可以理解為第一次第二次同時】
        } else {
            mostRight = cur.left;
            while (mostRight.right != null && mostRight.right != cur) {
                mostRight = mostRight.right;
            }
            if (mostRight.right == null) {//有左孩子，第一次訪問
                mostRight.right = cur;
                cur = cur.left;
            } else {
                if (pre != null && cur.val <= pre) {
                    return false;
                }
                pre = cur.val;
                mostRight.right = null;//有左孩子，第二次訪問
                cur = cur.right;
            }
        }
    }
    return true;
}

14、判斷完全二叉樹

完全二叉樹：要么是一顆滿二叉樹，要么葉子節(jié)點層是從左到右排布的

思路：1、通過層次遍歷來實現(xiàn)
2、如果一個節(jié)點只有右孩子 、沒有左孩子，直接返回false
3、如果出現(xiàn)了一個節(jié)點【只有左孩子，沒有右孩子】or【沒有左右孩子】，那么說明之后的節(jié)點都該是葉子節(jié)點了

 public boolean isCBT(TreeNode root) {
        if (root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        boolean leafStart = false;
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.remove();
            TreeNode left = cur.left;
            TreeNode right = cur.right;
            if (left == null && right != null) {//不符合條件，直接返回false
                return false;
            }
            if (leafStart && (left != null || right != null)) {//開始都是葉子節(jié)點了
                return false;
            }

            if (left != null) {
                queue.add(left);
            }
            if (right != null) {
                queue.add(right);
            }
            if ((left != null && right == null) || (left == null && right == null)) {//開始都是葉子節(jié)點了
                leafStart = true;
            }
        }
        return true;
    }

15、完全二叉樹的節(jié)點個數(shù)

要求時間復(fù)雜度小于 o(n)

思路：

1、一個完全二叉樹的高度可以通過求mostLeft孩子得到
2、一顆二叉樹的節(jié)點個數(shù)為
3、如果一個節(jié)點的右孩子的mostLeft的高度能夠達到整棵樹的高度，那么說明節(jié)點的左子樹是滿的；
4、如果右孩子的mostLeft不能到達整棵樹的高度，那么說明右子樹是滿的。

            1            
         /      \         
      2           3                         3   
    /   \        /   \                     /  \
  4      5      6     7                   6    7 
 / \    /  \   /                          /
8   9  10  11  12                       12

public int countNodes(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int treeHeight = height(root, 1);
    return count(root, treeHeight, 1);
}

/**
 * @param treeHeight 原始樹的高度
 * @param cur        當(dāng)前節(jié)點在第幾層
 */
public int count(TreeNode root, int treeHeight, int cur) {
    if (cur == treeHeight) {
        return 1;
    }
    int right = height(root.right, cur + 1);
    if (right == treeHeight) { //右節(jié)點的最左能到底，說明左子樹是滿的
        return (1 << (treeHeight - cur)) + count(root.right, treeHeight, cur + 1);
    } else { //不然右子樹是滿的
        return (1 << (treeHeight - cur - 1)) + count(root.left, treeHeight, cur + 1);
    }

}

//cur表示當(dāng)前節(jié)點在第幾層
public int height(TreeNode root, int cur) {
    while (root != null) {
        cur++;
        root = root.left;
    }
    return cur - 1;
}

16、！ 二叉樹的最近公共祖先

給定一個二叉樹, 找到該樹中兩個指定節(jié)點的最近公共祖先。

思路：1、首先找到給定節(jié)點到root節(jié)點的這樣一條路徑，保存在棧中
2、比較兩個棧，找到第一個相等的節(jié)點

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || p == null || q == null) {
        return null;
    }
    Stack<TreeNode> path1 = new Stack<>();
    Stack<TreeNode> path2 = new Stack<>();
    findPath(root, p, path1);
    findPath(root, q, path2);
    return getLastCom(path1, path2);
}

//尋找指定節(jié)點到root的路徑，保留在stack中
public boolean findPath(TreeNode root, TreeNode node, Stack<TreeNode> path) {
    if (root == null) {
        return false;
    }

    path.push(root);
    if (root == node) {
        return true;
    }
    if (findPath(root.left, node, path)) {
        return true;
    }
    if (findPath(root.right, node, path)) {
        return true;
    }
    path.pop();
    
    return false;
}

//找到兩個路徑中第一個相等的節(jié)點
public TreeNode getLastCom(Stack<TreeNode> pathLeft, Stack<TreeNode> pathRight) {
    while (pathLeft.size() != pathRight.size()) {
        if (pathLeft.size() > pathRight.size()) {
            pathLeft.pop();
        } else {
            pathRight.pop();
        }
    }
    while (!pathRight.isEmpty()) {
        TreeNode popleft = pathLeft.pop();
        TreeNode popRight = pathRight.pop();
        if (popleft == popRight) return popleft;
    }
    return null;
}   

17、樹的子結(jié)構(gòu)

B是A的子結(jié)構(gòu)， 即 A中有出現(xiàn)和B相同的結(jié)構(gòu)和節(jié)點值。

18、Trie (前綴樹)

Trie：前綴樹、字典樹
通過樹的形式，保留一堆字符串的信息，可以實現(xiàn)
1、判斷這些字符串中是否有以【"ab"】為前綴的字符串
2、判斷這些字符串中是否有【"ab"】這個字符串
3、判斷這些字符串中以【"ab"】為前綴的字符串有多少個
思路：
1、就是一個樹，把每一個字符串的char保留在樹的路徑上
2、在節(jié)點中增加以該節(jié)點為結(jié)尾的字符串的數(shù)量nodeEnd
3、在節(jié)點中增加有多少個字符串精活該節(jié)點prefix

前綴樹.png

class TrieNode {
    int prefix = 0;
    int nodeEnd = 0;
    HashMap<Character, TrieNode> nexts = new HashMap<>(); 
    //保留了當(dāng)前節(jié)點下的路徑，數(shù)據(jù)保留在Character，TrieNode是下一個節(jié)點
}

class Trie {
    TrieNode root;

    public Trie() {
        this.root = new TrieNode();
    }

    /**
     * Inserts a word into the trie.
     */
    public void insert(String word) {
        if (word == null || word.length() == 0) {
            return;
        }
        TrieNode cur = root;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            if (!cur.nexts.containsKey(ch)) {
                cur.nexts.put(ch, new TrieNode());
            }
            cur = cur.nexts.get(ch);
            cur.prefix++;
        }
        cur.nodeEnd++;
    }

    /**
     * Returns if the word is in the trie.
     */
    public int search(String word) {
        if (word == null || word.length() == 0) {
            return -1;
        }
        TrieNode cur = root;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            if(!cur.nexts.containsKey(ch)){
                return 0;
            }
            cur = cur.nexts.get(ch);
        }
        return cur.nodeEnd;
    }

    /**
     * Returns if there is any word in the trie that starts with the given prefix.
     */
    public int startsWith(String prefix) {
        if (prefix == null || prefix.length() == 0) {
            return -1;
        }
        TrieNode cur = root;
        for (int i = 0; i < prefix.length(); i++) {
            char ch = prefix.charAt(i);
            if(!cur.nexts.containsKey(ch)){
                return 0;
            }
            cur = cur.nexts.get(ch);
        }
        return cur.prefix;
    }

    /**
     *delete the infomation of the word  in the Trie
     */
    public boolean deleteWord(String word){
        //首先判斷Trie中是否有這個word
        if(search(word) <= 0){
            return false;
        }
        TrieNode cur = root;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            if(cur.nexts.get(ch).prefix == 1){
                cur.nexts.remove(ch);
                return true;
            }
            cur = cur.nexts.get(ch);
            cur.prefix--;
        }
        cur.nodeEnd--;
        return true;
    }
}