題目目錄

基礎面試題
- 二叉樹的前序遍歷
- 二叉樹的中序遍歷
- 二叉樹的后續遍歷結果
- 相同的樹
- 另一棵樹的子樹
- 二叉樹的最大深度
- 平衡二叉樹判斷
- 對稱二叉樹
進階面試題
- 二叉樹的遍歷及構建
- 二叉樹的分層遍歷
- 二叉樹的最近公共祖先
- 二叉搜索樹與雙向鏈表
- 從前序與中序遍歷序列構造二叉樹
- 從中序與后序遍歷序列構造二叉樹
- 根據二叉樹創建字串

基礎面試題

二叉樹的前序遍歷

題目：在線OJ

在這里插入圖片描述
思考：

首先，我們要了解，前序遍歷就是按照順序：根節點—左子樹—右子樹的方式遍歷樹(根左右)
在訪問左右子樹的時候，按照上述同樣的方法遍歷，因此我們可以考慮使用遞回來解決

創建一個 List，將根節點的元素加入到 List 中
遞回遍歷左子樹，把左子樹的遍歷結果加入到 List 中
遞回遍歷右子樹，把右子樹的遍歷結果加入到 List 中
最后回傳這個 List 即可

畫圖分析：

在這里插入圖片描述

代碼實作：

public List<Integer> preorderTraversal(TreeNode root) {
    //創建一個 List
    List<Integer> result = new ArrayList<>();
    if(root == null){
        //空樹回傳 一個空 List(元素個數為空，但不是null)
        return result;
    }
    //訪問根節點
    //把元素 add 到 List中
    result.add(root.val);

    //遞回遍歷左子樹,把左子樹的遍歷結果加入到List中
    result.addAll(preorderTraversal(root.left));
    //遞回遍歷右子樹,把右子樹的遍歷結果加入到List中
    result.addAll(preorderTraversal(root.right));

    return result;
}

二叉樹的中序遍歷

題目：在線OJ

在這里插入圖片描述
思考：

中序遍歷是按照順序：左子樹遍歷—根節點—右子樹遍歷的方式來遍歷樹(左根右)
同先序遍歷一樣，使用遞回解決

畫圖分析：

在這里插入圖片描述

代碼實作：

public List<Integer> inorderTraversal(TreeNode root) {
    //創建一個List
    List<Integer> result = new ArrayList<>();
    //空樹判斷
    if(root == null){
        return result;
    }
    //遞回遍歷左子樹
    result.addAll(inorderTraversal(root.left));
    //根節點
    result.add(root.val);
    //遞回遍歷右子樹
    result.addAll(inorderTraversal(root.right));

    return result;
}

二叉樹的后續遍歷結果

題目：在線OJ

在這里插入圖片描述

思考：

后續遍歷按照順序：左子樹遍歷—右子樹遍歷—根節點的遍歷方式來遍歷樹的(左右根)
實作程序參考前序遍歷

在這里插入圖片描述

代碼實作：

public List<Integer> postorderTraversal(TreeNode root) {
    //創建一個List
    List<Integer> result = new ArrayList<>();
    //空樹判斷
    if(root == null){
        return result;
    }
    //左子樹遍歷
    result.addAll(postorderTraversal(root.left));
    //右子樹遍歷
    result.addAll(postorderTraversal(root.right));
    //根節點
    result.add(root.val);
    
    return result;
}

相同的樹

題目：在線OJ

在這里插入圖片描述

思考：

先判斷根節點是否相同
遍歷判斷左子樹是否相同
遍歷判斷右子樹是否相同

以上條件均滿足時，則說明這兩棵樹相同

畫圖分析：

在這里插入圖片描述

代碼實作：

    public boolean isSameTree(TreeNode p, TreeNode q) {
        //兩棵樹全為空
        if(p == null && q == null){
            return true;
        }
        //一棵樹為空
        if(p == null || q == null){
            return false;
        }
        //兩棵樹均不為空
        //先判斷根節點是否相同
        if(p.val != q.val){
            return false;
        }
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }

另一棵樹的子樹

題目：在線OJ

在這里插入圖片描述

思考：

判斷一棵樹是不是另外一棵樹的子樹，本質就是在判斷一棵樹和另外一顆樹的某個子樹是否相等
可使用：遍歷 + 遞回拆分問題

先檢查 root 和 subRoot 是否相等
檢查 root.left 是否包含 subRoot
在檢查 root.right 是否包含 subRoot

上述滿足一個即可

畫圖：

在這里插入圖片描述
上述畫了左子樹的情況，若左子樹在不相同，接著再遞回右子樹與子樹比較，只要符合一種情況即可

代碼實作：

public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    //兩棵樹都為空
    if(root == null && subRoot == null){
        return true;
    }
    //一棵樹為空
    if(root == null || subRoot == null){
        return false;
    }
    boolean ret = false;
    //根節點的值 相同
    if(root.val == subRoot.val){
        ret = isSameTree(root,subRoot);
    }

    return ret || isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
}

二叉樹的最大深度

題目：在線OJ

在這里插入圖片描述

思考：

深度即：根節點到最遠葉子節點的層數
此處要注意深度是從 0 開始算，還是從 1 開始算
二叉樹的最大深度，即：max(左子樹深度，右子樹深度) + 1

代碼實作：

    public int maxDepth(TreeNode root) {
        //空樹
        if(root == null){
            return 0;
        }
        //左右子樹為空 只有根節點
        if(root.left == null && root.right == null){
            return 1;
        }
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        return 1 + (leftDepth > rightDepth ? leftDepth : rightDepth) ;
    }

平衡二叉樹判斷

題目：在線OJ

在這里插入圖片描述

思考：

先判斷空樹，或沒有子樹(只有根節點)—平衡
針對當前節點，求左右子樹高度差，看是否＞1
若＜1，再遞回判斷該樹的左右子樹，看高度差是否＜1

即：一棵樹是否平衡，先判斷該樹自己的左右子樹高度差是否 ≤ 1，還要滿足左右子樹也平衡才可以判斷該樹是平衡樹

畫圖分析：

在這里插入圖片描述

代碼實作：

public boolean isBalanced(TreeNode root) {
    //空樹
    if(root == null){
        return true;
    }
    //只有根節點  左右子樹為空
    if(root.left == null && root.right == null){
        return true;
    }
    //判斷當前節點對應的子樹是否平衡
    int leftDepth = maxDepth(root.left);
    int rightDepth = maxDepth(root.right);
    if(leftDepth - rightDepth > 1 || leftDepth - rightDepth < -1){
        return false;
    }
    return isBalanced(root.left) && isBalanced(root.right);
}

對稱二叉樹

題目：在線OJ

在這里插入圖片描述

思考：

判斷一棵樹是否對稱，本質上就是判斷該樹的所有子樹是否對稱

先判斷左右子樹( A B )的根節點是否相同
判斷 A.left 和 B.right 是否成鏡像關系
判斷 A.right 和 B.left 是否成鏡像關系

畫圖分析：

在這里插入圖片描述

代碼實作：

public boolean isSymmetric(TreeNode root) {
    //空樹
    if(root == null){
        return true;
    }
    return isMirror(root.left,root.right);
}

public boolean isMirror(TreeNode t1,TreeNode t2){
    //左右子樹都為空
    if(t1 == null && t2 == null){
        return true;
    }
    //一棵子樹為空
    if(t1 == null || t2 == null){
        return false;
    }
    //兩棵樹的根節點 值不相等
    if(t1.val != t2.val){
        return false;
    }
    return isMirror(t1.left,t2.right) && isMirror(t1.right,t2.left);
}

進階面試題

二叉樹的遍歷及構建

題目：在線OJ

在這里插入圖片描述

思考：

畫圖分析：

在這里插入圖片描述

代碼實作：

public class BuildTreeDemo {
    //靜態內部類
    static class TreeNode{
        public char val;
        TreeNode left;
        TreeNode right;

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

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //回圈輸入 在線OJ 一般都是多組用例
        while(scan.hasNext()){
            // s這個字串就對應一對形如“abc##de#g##f###” 的輸入資料
            String s = scan.next();
            TreeNode root = build(s);
            //中序遍歷
            inOrder(root);
            System.out.println();
        }
    }

    private static void inOrder(TreeNode root) {
            //若為空樹，直接回傳
            if(root == null){
                return;
            }
            //遞回訪問左子樹
            inOrder(root.left);
            //訪問根節點
            System.out.print(root.val+" ");
            //遞回訪問右子樹
            inOrder(root.right);
    }

    // index用來記錄訪問到 s 的哪個元素
    private static int index = 0;
    private static TreeNode build(String s) {
        index = 0;
        //先序遍歷
        return createTreePrevOrder(s);
    }

    private static TreeNode createTreePrevOrder(String s) {
        //獲取到當前處理到哪個節點
        char cur = s.charAt(index);
        if(cur == '#'){
            return null;
        }
        TreeNode root = new TreeNode(cur);
        index++;
        //下一個節點開始就是當前root左子樹的先序遍歷結果
        root.left = createTreePrevOrder(s);
        index++;
        root.right = createTreePrevOrder(s);
        return root;
    }
}

部分遞回程序分析：

在這里插入圖片描述

二叉樹的分層遍歷

題目：在線OJ

在這里插入圖片描述

遞回實作

思考：

創建一個變數 result 來存放我們的結果，最后 return result
(result 相當于一個二維陣列，result 0 對應第0層節點，result 1 對應第1層節點…)

代碼實作：

static List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
    //清空result 因為result是全域變數
    result.clear();
    //空樹判定
    if(root == null){
        return null;
    }
    // helper 方法輔助遞回，第二個引數表示當前層數 從 0 開始算
    helper(root,0);
    return result;
}
private void helper(TreeNode root, int level) {
    if(level == result.size()){
        result.add(new ArrayList<>());
    }
    //把當前節點添加到 result 中的合適位置
    result.get(level).add(root.val);
    if(root.left != null){
        helper(root.left,level + 1);
    }
    if(root.right != null){
        helper(root.right,level + 1);
    }
}

代碼分析：

在這里插入圖片描述

非遞回實作 (回圈)

思考：

使用一個佇列queue，先用來存放每一層的節點，并使用變數 level 來記錄該層有幾個元素
創建一個 list 來存放每一層節點，每遍歷完一層，將每一層都入佇列然后再出佇列并將其移除，即：把佇列里這一層的元素出佇列，并將其加入到 list 中
判斷左 / 右節點是否為空，來將下一層的元素加入到queue，佇列為空，停止回圈

代碼實作：

public List<List<Integer>> levelOrder(TreeNode root){
    //創建一個 result 來存放結果
    List<List<Integer>> result = new ArrayList<>();
    //空樹判斷
    if(root == null){
        return result;
    }
    //創建一個佇列，把根節點加入佇列
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    //佇列不為空，就一直回圈
    while ( !queue.isEmpty()){
        //定義為一個 list 來存放每一層節點
        List<Integer> list = new ArrayList<>();
        //佇列中當前所存在的數 即為當前層所有的數
        int level = queue.size();

        for (int i = 0; i < level; i++) {
            // 獲得并將第一個節點出佇列
            TreeNode cur = queue.poll();
            list.add(cur.val);
            if(cur.left != null){
                queue.add(cur.left);
            }
            if(cur.right != null){
                queue.add(cur.right);
            }
        }
        result.add(list);
    }
    return result;
}

二叉樹的最近公共祖先

題目：在線OJ

在這里插入圖片描述

方法1

思考：

若從某個節點開始，后續遍歷能把 p 和 q 都找到，說明該節點就是 p 和 q 的公共祖先
若從某個節點開始，后續遍歷能把 p 和 q 都找到，并且 p 和 q 不在同一子樹中，則當前節點就是 p 和 q 的最近公共祖先

代碼實作：

private TreeNode lca = null;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    //空樹判斷
    if(root == null){
        return null;
    }
    // findNode方法，在遞回尋找的程序中，找到結果，就將結果放到 lca 中
    findNode(root,p,q);
    //回傳 lca
    return lca;
}
//從 root 出發找 p q,只要找到 1 個，就回傳true，都找不到回傳false
private boolean findNode(TreeNode root, TreeNode p, TreeNode q) {
    //空樹判斷
    if(root == null){
        return false;
    }
    // 遞回 后序遍歷查找
    int left = findNode(root.left,p,q) ? 1 : 0;
    int right = findNode(root.right,p,q) ? 1 : 0;
    int mid = (root == p || root == q) ? 1 : 0;
    if(left + right + mid == 2){
        lca = root;
    }
    return (left + right +mid) > 0;
}

方法2

思考：

在左右子樹查找是否包含 p，q，如果 p 和 q 不在同一子樹中，那么此時的根節點就是最近公共祖先
如果左子樹包含 p 和 q，那么到當前節點的左子樹中查找，最近公共祖先在左子樹里面
如果右子樹包含 p 和 q，那么到當前節點的右子樹中查找，最近公共祖先在右子樹里面

代碼實作：

public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || p == root || q == root) {
        return root;
    }
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);

    if (left != null && right != null) {
        return root;
    }
    return left == null ? right : left;
}

二叉搜索樹與雙向鏈表

題目：在線OJ①，在線OJ②

在這里插入圖片描述

思考：

首先，我們要知道二叉搜索樹的概念
二叉搜索樹：是一種特殊的二叉樹，對于樹上的任意節點，它都滿足：左子樹中的所有節點都小于根節點，根節點又小于右子樹中的所有節點
因此，若對一個二叉搜索樹進行中序遍歷，遍歷結果就是一個有序陣列

遞回處理左子樹，把左子樹和當前節點連在一起
left 就是左子樹這個鏈表的根節點
遞回轉換右子樹，把當前節點和右子樹連在一起
right 相當于鏈表中的 next
最后回傳鏈表的頭節點

樹中沒有 next 和 prev，我們使用 right 指向下一個節點，left 指向上一個節點

代碼實作：

public TreeNode Convert(TreeNode pRootOfTree) {
    //空樹判斷
    if(pRootOfTree == null){
        return null;
    }
    //只有根節點
    if(pRootOfTree.left == null && pRootOfTree.right == null){
        return pRootOfTree;
    }
    //中序遍歷二叉搜索樹
    // 得到一個有序的陣列

    //遞回處理左子樹
    // left 就是左子樹這個鏈表的根節點
    TreeNode left = Convert(pRootOfTree.left);
    // 找到左子樹這個鏈表的尾節點
    TreeNode leftTail = left;
    // right 相當于 next
    while(leftTail != null && leftTail.right != null){
        leftTail = leftTail.right;
    }
    //回圈結束后，leftTail 指向左邊鏈表的尾部

    //把左子樹和當前節點連在一起
    if (left != null){
        leftTail.right = pRootOfTree;
        pRootOfTree.left = leftTail;
    }
    //遞回轉換右子樹
    TreeNode right = Convert(pRootOfTree.right);
    if (right != null){
        right.left = pRootOfTree;
        pRootOfTree.right = right;
    }
    //回傳鏈表的頭節點
    // left 為空，鏈表頭節點就是 root
    // left 非空，鏈表頭節點就是 left
    return left == null ? pRootOfTree : left;
}

從前序與中序遍歷序列構造二叉樹

題目：在線OJ

在這里插入圖片描述

思考：

先序遍歷：第一個訪問的節點一定是根節點，后面的節點就是左子樹 / 右子樹的根節點
中序遍歷：第一個訪問的節點是樹的最左側節點，左子樹一定在根節點左側，右子樹一定在根節點右側

由以上兩條規律，可以得出基本思路：

根據先序遍歷結果找到當前樹的根節點
拿到這個根節點到中序遍歷結果中查找，找到其左 / 右子樹
再根據劃分結果來構造樹

代碼實作：

private int index = 0; //表示當前訪問到 先序遍歷結果的第幾個元素
public TreeNode buildTree(int[] preorder, int[] inorder) {
    index = 0;
    return buildTreeHelper(preorder,inorder,0,inorder.length);
}
// [left,right) 區間表示 當前 preorder[index] 這個節點對應的子樹的中序遍歷結果
private TreeNode buildTreeHelper(int[] preorder, int[] inorder, int left, int right) {
    //中序遍歷結果為空，這個樹就是空樹
    if(left >= right){
        return null;
    }
    //遍歷元素結束
    if(left >= preorder.length){
        return null;
    }
    //根據當前節點的值創建根節點
    TreeNode root = new TreeNode(preorder[index]);
    //節點創建完畢，index++
    index++;
    //根據該節點在中序遍歷結果的位置，把 inorder 陣列劃分成兩個部分
    int pos = find(inorder,left,right,root.val);
    
    // [left,pos) 表示當前root左子樹的中序遍歷結果
    // [pos+1,right) 表示當前root右子樹的中序遍歷結果

    //遞回構建
    root.left = buildTreeHelper(preorder,inorder,left,pos);
    root.right = buildTreeHelper(preorder,inorder,pos+1,right);
    return root;
}
private int find(int[] inorder,int left,int right,int toFind){
    for (int i = left; i < right; i++) {
        if(inorder[i] == toFind){
            return i;
        }
    }
    return -1;
}

從中序與后序遍歷序列構造二叉樹

題目：在線OJ

在這里插入圖片描述

思考：

與上一題思路一樣
中序遍歷：第一個訪問的節點是樹的最左側節點，左子樹一定在根節點左側，右子樹一定在根節點右側 (左根右)
后序遍歷：最后一個訪問的節點一定是根節點 (左右根)

思路：

將后續遍歷結果逆置，就會變成一個鏡像先序遍歷結果 (根右左)
根據后序逆置遍歷結果找到當前樹的根節點
拿到這個根節點到中序遍歷結果中查找，找到其左 / 右子樹
再根據劃分結果來構造樹

根據二叉樹創建字串

題目：在線OJ

在這里插入圖片描述

思考：

此處需要注意需要省略的括號：

若一個樹左右子樹都為空，就不需要把左右子樹用 ( ) 表示
若一個樹的左子樹為空，右子樹非空，需要把左子樹用 ( ) 占位，且不能省略括號
若一個屬的左子樹非空，右子樹為空，則可以省略 ( )

代碼實作：

private StringBuilder sb = new StringBuilder();
public String tree2str(TreeNode root) {
    if(root == null){
        return ""; //此處注意不能為null，回傳的是一個空字串
    }
    helper2(root);
    sb.deleteCharAt(0);
    sb.deleteCharAt(sb.length() - 1);
    return sb.toString();
}
private void helper2(TreeNode root) {
    if(root == null){
        return;
    }
    //訪問根節點 即：追加字串
    sb.append("(");
    sb.append(root.val);

    //左子樹
    helper2(root.left);
    // 左子樹為空，右子樹非空
    if(root.left == null && root.right != null){
        sb.append("()");
    }
    //右子樹
    helper2(root.right);
    sb.append(")");
}

在這里插入圖片描述

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/308738.html

標籤：java

上一篇：業務中臺資料一致性方案

下一篇：Java中的資料型別

二叉樹相關面試題【資料結構】

題目目錄

基礎面試題

二叉樹的前序遍歷

二叉樹的中序遍歷

二叉樹的后續遍歷結果

相同的樹

另一棵樹的子樹

二叉樹的最大深度

平衡二叉樹判斷

對稱二叉樹

進階面試題

二叉樹的遍歷及構建

二叉樹的分層遍歷

二叉樹的最近公共祖先

二叉搜索樹與雙向鏈表

從前序與中序遍歷序列構造二叉樹

從中序與后序遍歷序列構造二叉樹

根據二叉樹創建字串