2019 算法面試相關(guān)(leetcode)--樹、二叉樹、二叉搜索樹

翻轉(zhuǎn)二叉樹
 二叉樹的前序遍歷
 二叉樹的中序遍歷
 二叉樹的后序遍歷
 驗證二叉搜索樹
 二叉樹的最近公共祖先
 二叉搜索樹的最近公共祖先

樹是一種數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=1）個有限結(jié)點組成一個具有層次關(guān)系的集合隘庄。把它叫做“樹”是因為它看起來像一棵倒掛的樹踢步，也就是說它是根朝上，而葉朝下的丑掺。它具有以下的特點：

每個結(jié)點有零個或多個子結(jié)點获印；沒有父結(jié)點的結(jié)點稱為根結(jié)點；每一個非根結(jié)點有且只有一個父結(jié)點街州；除了根結(jié)點外兼丰，每個子結(jié)點可以分為多個不相交的子樹

二叉樹(Binary Tree）是每個結(jié)點最多有兩個子樹的樹結(jié)構(gòu)。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）唆缴。二叉樹常被用于實現(xiàn)二叉查找樹和二叉堆鳍征。
一棵深度為k，且有2^k-1個節(jié)點的二叉樹面徽，稱為滿二叉樹艳丛。這種樹的特點是每一層上的節(jié)點數(shù)都是最大節(jié)點數(shù)。而在一棵二叉樹中趟紊，除最后一層外氮双，若其余層都是滿的，并且最后一層或者是滿的织阳，或者是在右邊缺少連續(xù)若干節(jié)點眶蕉，則此二叉樹為完全二叉樹砰粹。具有n個節(jié)點的完全二叉樹的深度為floor(log2n)+1唧躲。深度為k的完全二叉樹，至少有2k-1個葉子節(jié)點碱璃，至多有2k-1個節(jié)點弄痹。

二叉查找樹（Binary Search Tree），（又：二叉搜索樹嵌器，二叉排序樹）它或者是一棵空樹肛真，或者是具有下列性質(zhì)的二叉樹：若它的左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值爽航；若它的右子樹不空蚓让，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；它的左讥珍、右子樹也分別為二叉排序樹历极。

從二叉樹的定義來看，算是比較適用遞歸算法的數(shù)據(jù)結(jié)構(gòu)了

iOS:分別用OC和swift實現(xiàn)二叉樹,并繪制到屏幕上

二叉樹

function TreeNode(val) {
         this.val = val;
         this.left = this.right = null;
}

一衷佃、翻轉(zhuǎn)二叉樹

翻轉(zhuǎn)一棵二叉樹趟卸。

示例：

輸入：

    4
   /   \
  2     7
 / \   / \
1   3 6   9

輸出：

    4
   /   \
  7     2
 / \   / \
9   6 3   1

備注:
這個問題是受到 Max Howell 的原問題啟發(fā)的：

谷歌：我們90％的工程師使用您編寫的軟件(Homebrew)，但是您卻無法在面試時在白板上寫出翻轉(zhuǎn)二叉樹這道題，這太糟糕了锄列。

又是經(jīng)典的翻轉(zhuǎn)图云。
直接用遞歸解法，分別遞歸地交換左右子樹

var invertTree = function(root) {
   
   if(!root) return root

   let right = root.right
   
   root.right = invertTree(root.left)
   
   root.left = invertTree(right)

   return root
};

二邻邮、二叉樹的前序遍歷

給定一個二叉樹竣况，返回它的前序遍歷。

示例:

輸入: [1,null,2,3]

輸出: [1,2,3]
進階: 遞歸算法很簡單筒严，你可以通過迭代算法完成嗎帕翻？

前序遍歷首先訪問根結(jié)點然后遍歷左子樹，最后遍歷右子樹萝风。在遍歷左嘀掸、右子樹時，仍然先訪問根結(jié)點规惰，然后遍歷左子樹睬塌，最后遍歷右子樹。

簡單說其遍歷順序就是:根--左--右

使用遞歸可以很容易實現(xiàn)歇万。

var preorderTraversal = function(root) {
    
    return helper(root,[])
};

var helper = function(root,nums){

    if(!root) return nums

    nums.push(root.val)

    helper(root.left,nums)

    helper(root.right,nums)

    return nums
}

不過題目有要求用迭代算法揩晴，這里我們可以想到之前提過的數(shù)據(jù)結(jié)構(gòu):棧
我們可以先將父結(jié)點的值放到數(shù)組里，然后將父節(jié)點入棧贪磺，等遍歷完左子樹硫兰，再出棧，去遍歷右子樹寒锚。

var preorderTraversal = function(root){

    let treeStack = []

    let res = []

    while(root || treeStack.length){

        while(root){

            res.push(root.val)

            treeStack.push(root)

            root = root.left
        }

        if(treeStack.length){

            root = treeStack.pop()

            root = root.right
        }
    }

    return res
}

三劫映、二叉樹的中序遍歷

給定一個二叉樹，返回它的中序遍歷刹前。

示例:

輸入: [1,null,2,3]

輸出: [1,3,2]
進階: 遞歸算法很簡單泳赋，你可以通過迭代算法完成嗎？

中序遍歷首先遍歷左子樹喇喉，然后訪問根結(jié)點祖今，最后遍歷右子樹。若二叉樹為空則結(jié)束返回拣技，否則：

（1）中序遍歷左子樹

（2）訪問根結(jié)點

（3）中序遍歷右子樹

簡單說其遍歷順序就是:左--根--右

同理千诬，用遞歸也可以很簡單的實現(xiàn)。

var inorderTraversal = function(root) {

    return helper(root,[])
};

var helper = function(root,nums){

    if(!root) return nums

    helper(root.left,nums)

    nums.push(root.val)

    helper(root.right,nums)

    return nums
}

如果不用遞歸膏斤，用迭代呢徐绑？一樣，也可以用棧去實現(xiàn)掸绞，先把父結(jié)點入棧泵三，去遍歷左子樹耕捞，然后出棧將父節(jié)點放進數(shù)組，在同樣去遍歷右子樹

var inorderTraversal = function(root){

   let treeStack = []

    let res = []

    while(root || treeStack.length){

        while(root){

            treeStack.push(root)

            root = root.left
        }

        if(treeStack.length){

            root = treeStack.pop()

            res.push(root.val)

            root = root.right
        }
    }

    return res
}

四烫幕、二叉樹的后序遍歷

給定一個二叉樹俺抽，返回它的后序遍歷。

示例:

輸入: [1,null,2,3]

輸出: [3,2,1]
進階: 遞歸算法很簡單较曼，你可以通過迭代算法完成嗎磷斧？

后序遍歷首先遍歷左子樹，然后遍歷右子樹捷犹，最后訪問根結(jié)點弛饭，在遍歷左、右子樹時萍歉，仍然先遍歷左子樹侣颂，然后遍歷右子樹，最后遍歷根結(jié)點枪孩。即：
若二叉樹為空則結(jié)束返回憔晒，否則：

（1）后序遍歷左子樹

（2）后序遍歷右子樹

（3）訪問根結(jié)點

簡單說其遍歷順序就是:左--右--根

和前序中序一樣，用遞歸也可以很簡單的實現(xiàn)蔑舞。

var postorderTraversal = function(root) {
    
    return helper(root,[])
};

var helper = function(root,nums){

    if(!root) return nums

    helper(root.left,nums)

    helper(root.right,nums)

    nums.push(root.val)

    return nums
}

那如果不用遞歸用迭代呢拒担？
leetcode上的前序中序遍歷兩道題都是標(biāo)注的中等難度，而這道題卻是標(biāo)注成困難難度攻询。
因為如果還是用之前的思路即還是用棧从撼，是沒辦法直接實現(xiàn)的。
我們可以以根-右-左順序入棧钧栖，然后一直向左遍歷低零，直至左右子樹都為空。出棧并保存到數(shù)組中桐经，然后一直重復(fù)以上毁兆，這里需要注意的是，由于父結(jié)點已經(jīng)遍歷過了阴挣，這里一直出棧會造成死循環(huán)。所以我們還需要引入一個參數(shù)pre纺腊，來記錄上次遍歷的樹畔咧，如果是棧尾的左右子樹，則說明該結(jié)點已經(jīng)遍歷過揖膜，不再重復(fù)遍歷誓沸。

var postorderTraversal = function(root) {
    
    if(!root) return []
    
    let treeStack = [root]

    let res = []

    let pre

    while(treeStack.length){

        root = treeStack[treeStack.length - 1]

        if((!root.left && !root.right) || (pre &&(pre == root.left || pre == root.right))){

            res.push(root.val)

            treeStack.pop()

            pre = root

        }else{

            if(root.right) treeStack.push(root.right)

            if(root.left) treeStack.push(root.left)
        }
    }

    return res
}

五、驗證二叉搜索樹

給定一個二叉樹壹粟，判斷其是否是一個有效的二叉搜索樹拜隧。

假設(shè)一個二叉搜索樹具有如下特征：

節(jié)點的左子樹只包含小于當(dāng)前節(jié)點的數(shù)宿百。
節(jié)點的右子樹只包含大于當(dāng)前節(jié)點的數(shù)。
所有左子樹和右子樹自身必須也是二叉搜索樹洪添。
示例 1:

輸入:

    2
   / \
  1   3

輸出: true
示例 2:

輸入:

輸出: false
解釋: 輸入為: [5,1,4,null,null,3,6]垦页。
根節(jié)點的值為 5 ，但是其右子節(jié)點值為 4 干奢。

驗證二叉搜索樹痊焊，其實就是驗證其是否有序，我們可以對其進行中序遍歷忿峻，如果遍歷后的數(shù)據(jù)是有序的薄啥，則說明是二叉搜索樹，反之則不是逛尚。

var isValidBST = function(root) {

    if(!root) return true

    let nums = []

    helper(root,nums)
    
    for(let i = 0; i < nums.length - 1; i++){
        
        if(nums[i] >= nums[i + 1]) return false
    }

    return true
}
var helper = function(root,nums){

    if(!root) return

    helper(root.left,nums)

    nums.push(root.val)

    helper(root.right,nums)
}

那么能不能用o(1)的空間復(fù)雜度來解決呢垄惧？事實上我們沒必要把數(shù)據(jù)都保存下來，對于右子樹而言绰寞，只要所有右子樹都大于其父節(jié)點即可赘艳，同理，所有左子樹小于其父節(jié)點即可克握。
我們可以用兩個變量：min和max蕾管，對于左子樹，則判斷是否小于min菩暗；對于右子樹掰曾，則判斷是否大于max
然后不斷遞歸遍歷，同時更新min和max

var isValidBST = function(root) {

    return helper(root,undefined,undefined)
}

var helper = function(root,min,max){

    if(!root ) return true

    if(min != undefined && root.val <= min) return false

    if(max != undefined && root.val >= max) return false

    return helper(root.right,root.val,max) && helper(root.left,min,root.val)
}

六停团、二叉樹的最近公共祖先

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

百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結(jié)點 p、q佑稠，最近公共祖先表示為一個結(jié)點 x秒梅，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節(jié)點也可以是它自己的祖先）舌胶±κ瘢”

例如，給定如下二叉樹: root = [3,5,1,6,2,0,8,null,null,7,4]

image

示例 1:

輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
輸出: 3
解釋: 節(jié)點 5 和節(jié)點 1 的最近公共祖先是節(jié)點 3幔嫂。

示例 2:

輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
輸出: 5
解釋: 節(jié)點 5 和節(jié)點 4 的最近公共祖先是節(jié)點 5辆它。因為根據(jù)定義最近公共祖先節(jié)點可以為節(jié)點本身。

說明:

所有節(jié)點的值都是唯一的履恩。
p锰茉、q 為不同節(jié)點且均存在于給定的二叉樹中。

首先可以確定如果root為null或者p或q是根節(jié)點切心，那么說明最近的公共祖先就是根結(jié)點root飒筑。
我們同樣可以使用遞歸去實現(xiàn),分別遞歸左右結(jié)點片吊，將其設(shè)為根節(jié)點，如果返回null协屡，說明公共祖先在另一側(cè)俏脊，如果都為null，說明公共結(jié)點就是root

var lowestCommonAncestor = function(root, p, q) {

    if(root == null || root == p || root == q) return root

    let left = lowestCommonAncestor(root.left,p,q)

    let right = lowestCommonAncestor(root.right,p,q)

    return !left ? right : (!right ? left : root)
}

或者我們可以同時分別求p和q的最近祖先

var findLowestAncestor = function(root,p){

    if(root == null || root == p || root.left == p || root.right == p) return root

    return findLowestAncestor(root.left,p) || findLowestAncestor(root.right,p)
}

一層一層往上遍歷著瓶，直到p和q的祖先相遇

var lowestCommonAncestor = function(root, p, q) {

    let qSet = new Set()
    
    qSet.add(q)

    while(p != q){

        if(qSet.has(p)) return p

        while(q != root){

            q = findAncestor(root,q)

            if(p == q) return p
            
            qSet.add(q)
        }
        
        p = findAncestor(root,p)
    }
    
    return p
};

七联予、二叉搜索樹的最近公共祖先

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

百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結(jié)點 p材原、q沸久，最近公共祖先表示為一個結(jié)點 x，滿足 x 是 p余蟹、q 的祖先且 x 的深度盡可能大（一個節(jié)點也可以是它自己的祖先）卷胯。”

例如威酒，給定如下二叉搜索樹: root = [6,2,8,0,4,7,9,null,null,3,5]

image

示例 1:

輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
輸出: 6
解釋: 節(jié)點 2 和節(jié)點 8 的最近公共祖先是 6窑睁。

示例 2:

輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
輸出: 2
解釋: 節(jié)點 2 和節(jié)點 4 的最近公共祖先是 2, 因為根據(jù)定義最近公共祖先節(jié)點可以為節(jié)點本身。

說明:

所有節(jié)點的值都是唯一的葵孤。
p担钮、q 為不同節(jié)點且均存在于給定的二叉搜索樹中。

題目中的p和q有可能兩個都在同側(cè)尤仍，在遞歸的過程中箫津，另一側(cè)則沒有必要去遞歸了，但因為二叉樹無序宰啦，所以上邊的算法沒辦法去判斷苏遥，就算p和q不在另一側(cè)，也只能繼續(xù)遞歸下去赡模。
而在二叉搜索樹中田炭，上邊的那個算法就可以優(yōu)化下
如果p和q都小于root的值，則說明p和q都在左側(cè)漓柑，向左邊遞歸即可教硫；
如果p和q都大于root的值，則說明p和q都在右側(cè)欺缘，向右邊遞歸即可栋豫；
否則，就說明p和q在root的左右兩側(cè)谚殊，則其最近公共祖先就是root。
如果(root.val - p.val) 和 (root.val - q.val)的積是正的蛤铜，則說明他們在同一側(cè)

var lowestCommonAncestor = function(root, p, q) {
  
   return (root.val - p.val) * (root.val - q.val) <= 0 ? root : lowestCommonAncestor(root.val >= q.val ? root.left : root.right, p, q)
};

這里當(dāng)然也可以不用遞歸

var lowestCommonAncestor = function(root, p, q) {

    while ((root.val - p.val) * (root.val - q.val) > 0) root = p.val < root.val ? root.left : root.right

    return root
};

2019 算法面試相關(guān)(leetcode)--樹、二叉樹岖食、二叉搜索樹

2019 算法面試相關(guān)(leetcode)--樹莹妒、二叉樹名船、二叉搜索樹

一衷佃、翻轉(zhuǎn)二叉樹

二邻邮、二叉樹的前序遍歷

三劫映、二叉樹的中序遍歷

四烫幕、二叉樹的后序遍歷

五、驗證二叉搜索樹

六停团、二叉樹的最近公共祖先

七联予、二叉搜索樹的最近公共祖先

2019 算法面試相關(guān)(leetcode)--樹莹妒、二叉樹名船、二叉搜索樹

一衷佃、 翻轉(zhuǎn)二叉樹

二邻邮、 二叉樹的前序遍歷

三劫映、 二叉樹的中序遍歷

四烫幕、二叉樹的后序遍歷

五、 驗證二叉搜索樹

六停团、 二叉樹的最近公共祖先

七联予、 二叉搜索樹的最近公共祖先

一衷佃、翻轉(zhuǎn)二叉樹

二邻邮、二叉樹的前序遍歷

三劫映、二叉樹的中序遍歷

五、驗證二叉搜索樹

六停团、二叉樹的最近公共祖先

七联予、二叉搜索樹的最近公共祖先