我的面試準(zhǔn)備過(guò)程--二叉樹(shù)(更新中)

Amio 發(fā)布于2019-08-16 10:36 / 825人閱讀

摘要：寫(xiě)在最前面導(dǎo)師貪腐出逃美國(guó)，兩年未歸，可憐了我。拿了小米和美團(tuán)的，要被延期，失效，工作重新找。把準(zhǔn)備過(guò)程紀(jì)錄下來(lái)，共勉。

寫(xiě)在最前面

導(dǎo)師貪腐出逃美國(guó)，兩年未歸，可憐了我。拿了小米和美團(tuán)的offer，要被延期，offer失效，工作重新找。把準(zhǔn)備過(guò)程紀(jì)錄下來(lái)，共勉。

二叉樹(shù)的基礎(chǔ) 結(jié)點(diǎn)定義

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

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

二叉樹(shù)的遍歷 前序遍歷

前序遍歷，遞歸法

public static void preorderTraversalRec(TreeNode root) {
    if(root == null){
        return;
    }

    System.out.print(root.val + " ");
    preorderTraversalRec(root.left);
    preorderTraversalRec(root.right);
}

前序遍歷，迭代法
思路：借助一個(gè)棧

public static void preorderTraversal(TreeNode root) {
    if(null == root){
        return;
    }

    Stack stack = new Stack<>();
    stack.push(root);

    while(!stack.empty()){
        TreeNode cur = stack.pop();

        System.out.println(cur.val);

        //后入先出，因而先壓右結(jié)點(diǎn)，再壓左結(jié)點(diǎn)
        if(null != cur.right){
            stack.push(cur.right);
        }

        if(null != cur.left){
            stack.push(cur.left);
        }

    }
}

中序遍歷

中序遍歷，遞歸法

public static void inorderTraversalRec(TreeNode root) {
    if(null == root){
        return;
    }

    inorderTraversalRec(root.left);
    System.out.print(root.val + " ");
    inorderTraversalRec(root.right);

}

中序遍歷，迭代法

public static void inorderTraversal(TreeNode root) {
    if(null == root){
        return;
    }

    Stack stack = new Stack<>();
    TreeNode cur = root;

    while(true){
        while(cur != null){
            stack.push(cur);
            cur = cur.left;
        }

        if(stack.empty()){
            break;
        }

        cur = stack.pop();
        System.out.print(cur.val + " ");
        cur = cur.right;
    }

}

后序遍歷

后序遍歷，遞歸法

public static void postorderTraversalRec(TreeNode root) {
    if(null == root){
        return;
    }

    postorderTraversalRec(root.left);
    postorderTraversalRec(root.right);
    System.out.print(root.val + " ");
}

后序遍歷，迭代法

public static void postorderTraversal(TreeNode root){
    if(null == root){
        return;
    }

    Stack s = new Stack();
    Stack output = new Stack<>();

    s.push(root);
    while(!s.empty()){
        TreeNode cur = s.pop();
        output.push(cur);

        if(cur.left != null){
            s.push(cur.left);
        }

        if(cur.right != null){
            s.push(cur.right);
        }
    }

    while(!output.empty()){
        System.out.print(output.pop().val + " ");
    }
}

分層遍歷

public static void levelTraversal(TreeNode root) {
    if(null == root){
        return;
    }

    Queue queue = new LinkedList<>();
    queue.push(root);

    while(!queue.empty()){
        TreeNode cur = queue.removeFirst();
        System.out.print(cur.val + " ");

        if(cur.left != null){
            queue.add(cur.left);
        }

        if(cur.right != null){
            queue.add(cur.right);
        }
    }
}

求二叉樹(shù)結(jié)點(diǎn)的個(gè)數(shù)

遞歸解法時(shí)間復(fù)雜度O(n)

public static int getNodeNumRec(TreeNode root){
    if(null != root){
        return 0;
    }

    return getNodeNumRec(root.left) + getNodeNumRec(root.right) + 1;
}

迭代解法時(shí)間復(fù)雜度O(n)
思路：與層級(jí)遍歷相同，遍歷的過(guò)程中紀(jì)錄結(jié)點(diǎn)數(shù)

public static int getNodeNum(TreeNode root){
    if(null != root){
        return 0;
    }

    int count = 1;
    Queue queue = LinkedList<>();
    queue.add(root);

    while(!queue.empty()){
        TreeNode cur = queue.remove();

        if(cur.left != null){
            queue.add(cur.left);
            count++;
        }

        if(cur.right != null){
            queue.add(cur.right);
            count++;
        }
    }

    return count;
}

求二叉樹(shù)的深度（高度）

遞歸解法時(shí)間復(fù)雜度O(n)

public static int getDepthRec(TreeNode root) {
    if(null != root){
        return 0;
    }

    int leftDepth = getDepthRec(root.left);
    int rightDepth = getDepthRec(root.right);
    return Math.max(leftDepth, rightDepth) + 1;
}

迭代解法時(shí)間復(fù)雜度O(n)

public static int getDepth(TreeNode root){
    if(null != root){
        return 0;
    }

    int depth = 0;
    int curLevelNodes = 1;
    int nextLevelNodes = 0;

    Queue queue = new LinkedList<>();
    queue.add(root);

    while(!queue.empty()){
        TreeNode cur = queue.remove();
        curLevelNodes--;

        if(cur.left != null){
            nextLevelNodes++;
            queue.add(cur.left);
        }

        if(cur.right != null){
            nextLevelNodes++；
            queue.add(cur.right);
        }

        if(curLevelNodes == 0){
            depth++;
            curLevelNodes = nextLevelNodes;
            nextLevelNodes = 0;
        }
    }

    return depth；
}

求二叉樹(shù)第K層的節(jié)點(diǎn)個(gè)數(shù)

遞歸解法
思路：求以root為根的k層節(jié)點(diǎn)數(shù)目等價(jià)于求以root左孩子為根的k-1層（因?yàn)樯倭藃oot那一層）節(jié)點(diǎn)數(shù)目加上以root右孩子為根的k-1層（因?yàn)樯倭藃oot那一層）節(jié)點(diǎn)數(shù)目

public static int getNodeNumKthLevelRec(TreeNode root, int k) {
    if(null != root || k < 0){
        return 0;
    }

    if(k == 1){
        return 1;
    }

    int leftNodeNumKth = getNodeNumKthLevelRec(root.left, k - 1);
    int rightNodeNumKth = getNodeNumKthLevelRec(root.right, k - 1);
    return leftNodeNumKth + rightNodeNumKth;
}

迭代法
思路：與求解樹(shù)深度的解法相同，需要

public static int getNodeNumKthLevel(TreeNode root, int k){
    if(root == null || k < 0){
        return 0;
    }

    Queue queue = new LinkedList<>();
    queue.add(root);

    int curLevelNodes = 1;
    int nextLevelNodes = 0;

    while(!queue.empty && k > 0){
        TreeNode cur = queue.remove();
        curLevelNodes--;

        if(cur.left != null){
            queue.add(cur.left);
            nextLevelNodes++;
        }

        if(cur.right != null){
            queue.add(cur.right);
            nextLevelNodes++;
        }

        if(curLevelNodes == 0){
            curLevelNodes = nextLevelNodes;
            nextLevelNodes = 0;
            k--;
        }
    }

    return curLevelNodes;
}

求二叉樹(shù)中葉子節(jié)點(diǎn)的個(gè)數(shù)

迭代法

public static int getNodeNumLeaf(TreeNode root) {
    if(root == null){
        return 0;
    }

    Queue queue = new LinkedList<>();
    queue.add(root);

    int leafNodeNum = 0;

    while(!queue.empty()){
        TreeNode cur = queue.remove();

        if(cur.left != null){
            queue.add(cur.left);
        }

        if(cur.right != null){
            queue.add(cur.right);
        }

        if(cur.left == null && cur.right = null){
            leafNodeNum++;
        }
    }
    return leafNodeNum;
}

兩個(gè)二叉樹(shù)之間的關(guān)系 判斷兩棵二叉樹(shù)是否相同的樹(shù)。

遞歸法

public static boolean isSameRec(TreeNode r1, TreeNode r2) {
    if(r1 == null && r2 == null){
        return true;
    }

    if(r1 == null || r2 == null){
        return false;
    }

    if(r1.val != r2.val){
        return false;
    }

    boolean leftRes = isSameRec(r1.left, r2.left);
    boolean rightRes = isSameRec(r1.right, r2.right);

    return leftRes && rightRes;
}

迭代法
思路：遍歷一遍，比對(duì)即可

public static boolean isSame(TreeNode r1, TreeNode r2) {
    if(r1 == null && r2 == null){
        return true;
    }

    if(r1 == null || r2 == null){
        return false;
    }

    Stack s1 = new Stack<>();
    Stack s2 = new Stack<>();

    s1.push(r1);
    s2.push(r2);

    while(!s1.empty() && !s2.empty()){
        TreeNode n1 = s1.pop();
        TreeNode n2 = s2.pop();

        if(n1 == null && n2 == null){
            continue;
        }else if(n1 != null && n2 != null && n1.val == n2.val){
            s1.push(n1.right);
            s1.push(n1.left);
            s2.push(n2.right);
            s2.push(n2.left);
        }else{
            return false;
        }
    }
    return true;
 }

判斷二叉樹(shù)是不是平衡二叉樹(shù)

遞歸解法

思路：
(1）如果二叉樹(shù)為空，返回真
(2）如果二叉樹(shù)不為空，如果左子樹(shù)和右子樹(shù)都是AVL樹(shù)并且左子樹(shù)和右子樹(shù)高度相差不大于1，返回真，其他返回假

public static boolean isAVLRec(TreeNode root) {
    if(root == null){
        return true;
    }

    if(Math.abs(getDepthRec(root.left) - getDepthRec(root.right)) > 1){
        return false;
    }

    return isAVLRec(root.left) && isAVLRec(root.right);
}

樹(shù)的鏡像 判斷兩個(gè)樹(shù)是否互相鏡像

    public static boolean isMirrorRec(TreeNode r1, TreeNode r2){
   if(r1 == null && r2 == null){
       return true;
   }

   if(r1 == null || r2 == null){
       return false;
   }

   if(r1.val != r2.val){
       return false;
   }

   return isMirrorRec(r1.left, r2.right) && isMirrorRec(r1.right, r2.left);
    }

求樹(shù)的鏡像

遞歸解法
（1）如果二叉樹(shù)為空，返回空
（2）如果二叉樹(shù)不為空，求左子樹(shù)和右子樹(shù)的鏡像，然后交換左子樹(shù)和右子樹(shù)

破壞原來(lái)的樹(shù)

public static TreeNode mirrorRec(TreeNode root) {
if(root == null){
   return null;
}

TreeNode left = mirrorRec(root.left);
TreeNode right = mirrorRec(root.right);

root.left = right;
root.right = left;
return root;
}

2.保存原來(lái)的樹(shù)

public static TreeNode mirrorCopyRec(TreeNode root) {
    if(root == null){
        return null;
    }

    TreeNode newRoot = new TreeNode(root.val);
    newRoot.left = mirrorCopyRec(root.right);
    newRoot.right = mirrorCopyRec(root.left);

    return newRoot;

}

迭代解法

破壞原來(lái)的樹(shù)

public static void mirror(TreeNode root) {
    if(root == null){
        return;
    }

    Stack stack = new Stack();
    stack.push(root);

    while(!stack.empty()){
        TreeNode cur = stack.pop();

        TreeNode tmp = cur.left;
        cur.left = cur.right;
        cur.right = tmp;

        if(cur.left != null){
            stack.push(cur.left);
        }

        if(cur.right != null){
            stack.push(cur.right);
        }
    }
}

不能破壞原來(lái)的樹(shù)，返回一個(gè)新的鏡像樹(shù)

public static TreeNode mirrorCopy(TreeNode root){
    if(root == null){
        return null;
    }

    Stack stack = new Stack<>();
    Stack newStack = new Stack<>();
    stack.push(root);
    TreeNode newRoot = new TreeNode(root.val);
    newStack.push(newRoot);

    while(!stack.empty()){
        TreeNode cur = stack.pop();
        TreeNode newCur = newStack.pop();

        if(cur.left != null){
            stack.push(cur.left);
            newCur.right = new TreeNode(cur.left.val);
            newStack.push(newCur.right);
        }

        if(cur.right != null){
            stack.push(cur.right);
            newCur.left = new TreeNode(cur.right.val);
            newStack.push(newCur.left);
        }
    }
    return newRoot;
}

求二叉樹(shù)中兩個(gè)節(jié)點(diǎn)的最低公共祖先節(jié)點(diǎn)

遞歸法
思路：1. 如果其中一個(gè)結(jié)點(diǎn)為根結(jié)點(diǎn)，則返回根結(jié)點(diǎn)

如果一個(gè)左子樹(shù)找到，一個(gè)在右子樹(shù)找到，則說(shuō)明root是唯一可能的最低公共祖先

其他情況是要不然在左子樹(shù)要不然在右子樹(shù)

public static TreeNode getLastCommonParentRec(TreeNode root, TreeNode n1, TreeNode n2) {
    if (root == null || n1 == null || n2 == null) {
        return null;
    }

    if(root.equals(n1) || root.equals(n2)){
        return root;
    }

    TreeNode commonInLeft = getLastCommonParentRec(root.left, n1, n2);
    TreeNode commonInRight = getLastCommonParentRec(root.right, n1, n2);
    if(commonInLeft != null && commonInRight != null){
        return root;
    }

    if(commonInLeft == null){
        return commonInRight;
    }

    if(commonInRight == null){
        return commonInLeft;
    }
    return root;
}

迭代法

public static TreeNode getLastCommonParent(TreeNode root, TreeNode n1, TreeNode n2){
    if(root == null || n1 == null || n2 == null){
        return null;
    }

    List list1= new ArrayList<>();
    List list2 = new ArrayList<>();

    boolean res1 = getNodePath(root, n1, list1);
    boolean res2 = getNodePath(root, n2, list2);

    if(!res1 || !res2){
        return null;
    }

    Iterator iter1 = list1.iterator();
    Iterator iter2 = list2.iterator();
    TreeNode last = null;

    while(iter1.hasNext() && iter2.hasNext()){
        TreeNode tmp1 = iter1.next();
        TreeNode tmp2 = iter2.next();

        if(tmp1 == tmp2){
            last = tmp1;
        }else{
            break;
        }
    }
    return last;
}

private static boolean getNodePath(TreeNode root, TreeNode n, List path){
    if(root == null){
        return false;
    }

    path.add(root);
    if(root == n){
        return true;
    }

    boolean found = false;
    found = getNodePath(root.left, n, path);

    if(!found){
        found = getNodePath(root.right, n, path);
    }

    if(!found){
        path.remove(root);
    }

    return found;
}

本章參考http://blog.csdn.net/fightfor...

GPU云服務(wù)器云服務(wù)器二叉樹(shù) python二叉樹(shù) 平衡二叉樹(shù) 實(shí)現(xiàn)二叉樹(shù)

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/70112.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

Amio

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

安裝tensorflow指定版本

閱讀 2490·2023-04-25 21:41
云主機(jī)什么用-云主機(jī)的優(yōu)缺點(diǎn)是什么呢？

閱讀 1660·2021-09-22 15:17
堅(jiān)持不懈續(xù)集 (二) 初學(xué)者挑戰(zhàn)學(xué)習(xí)Python編程30天

閱讀 1931·2021-09-22 10:02
Totyun：香港VPS，日本VPS，全場(chǎng)5折優(yōu)惠，2核2G內(nèi)存，10Mbps不限流量，$6/月起

閱讀 2447·2021-09-10 11:21
DOM層級(jí)順序與z-index

閱讀 2586·2019-08-30 15:53
電競(jìng)CSGO數(shù)據(jù)API接口 - 【戰(zhàn)隊(duì)數(shù)據(jù)列表】API調(diào)用示例代碼

閱讀 1006·2019-08-30 15:44
初識(shí)canvas

閱讀 959·2019-08-30 13:46
css實(shí)現(xiàn)一個(gè)垂直水平居中彈窗的三種方式

閱讀 1149·2019-08-29 18:36

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

我的面試準(zhǔn)備過(guò)程--二叉樹(shù)(更新中)

相關(guān)文章

**前端該如何準(zhǔn)備數(shù)據(jù)結(jié)構(gòu)和算法？**

**使用JavaScript完成二叉樹(shù)的一些基本操作**

LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

準(zhǔn)備下次編程面試前你應(yīng)該知道的數(shù)據(jù)結(jié)構(gòu)

發(fā)表評(píng)論

0條評(píng)論

Amio

男|高級(jí)講師

TA的文章

安裝tensorflow指定版本

云主機(jī)什么用-云主機(jī)的優(yōu)缺點(diǎn)是什么呢？

堅(jiān)持不懈續(xù)集 (二) 初學(xué)者挑戰(zhàn)學(xué)習(xí)Python編程30天

Totyun：香港VPS，日本VPS，全場(chǎng)5折優(yōu)惠，2核2G內(nèi)存，10Mbps不限流量，$6/月起

DOM層級(jí)順序與z-index

電競(jìng)CSGO數(shù)據(jù)API接口 - 【戰(zhàn)隊(duì)數(shù)據(jù)列表】API調(diào)用示例代碼

初識(shí)canvas

css實(shí)現(xiàn)一個(gè)垂直水平居中彈窗的三種方式

最新活動(dòng)

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

我的面試準(zhǔn)備過(guò)程--二叉樹(shù)(更新中)

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！