頻率很高的手寫代碼面試題--二叉樹類型(下)

頻率很高的面試題--二叉樹類型

- - 1、相同的樹
  - 2、驗證二叉搜尋樹
  - 3、對稱二叉樹
  - 4、左葉子之和
  - 5、二叉樹的右視圖
  - 6、序列化二叉樹
  - 7、二叉樹路徑總和
  - 8、求根到葉子節點數字之和
  - 9、最小高度樹

1、相同的樹

給定兩個二叉樹，編寫一個函數來檢驗它們是否相同

如果兩個樹在結構上相同，并且節點具有相同的值，則認為它們是相同的。

思路：

（1）如果兩個節點都為空，則傳回True

（2）如果都不為空且相等，則要進行遞歸往左和往右周遊

（3）如果上述條件都不滿足，假如：一個為空、一個不為空、或者節點值不相等，這些情況直接傳回False

def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if p==None and q==None:
            return True
        
        if p!=None and q!=None and p.val ==q.val:
            return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
        else:
            return False

方法二：

def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if q and p:
            return p.val==q.val and self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
        # 如果他們都為空則傳回True,否則傳回False
        return q is p
        # return q == p

2、驗證二叉搜尋樹

給定一個二叉樹，判斷其是否是一個有效的二叉搜尋樹。

假設一個二叉搜尋樹具有如下特征：

節點的左子樹隻包含小于目前節點的數。

節點的右子樹隻包含大于目前節點的數。

所有左子樹和右子樹自身必須也是二叉搜尋樹。

示例

輸入:

2
 / \
1   3
輸出: true
示例

輸入:

5
 / \
1   4
   / \
  3   6
  
輸出: false
解釋: 輸入為: [5,1,4,null,null,3,6]
根節點的值為 5 ，但是其右子節點值為 4

驗證二叉樹其實最簡單的思想就是進行中序周遊的判斷，因為二叉樹中序的序列式遞增的序列。

但是我們在比較的時候，不能用根節點和左右子樹去比較，這其實是一個誤區！

比如下面案例：

思路：遞歸思想。首先看的根節點，根節點的值不能和1,7比較，7應該介于int 和 -int 之間

然後如果滿足，則往左遞歸，這時候和1節點比較的是 -int 和 5，再往左遞歸發現是none，則傳回，然後往右遞歸也是空，傳回。

接着，還是往右遞歸，這時候root 節點值為7，節點7不能和6,8比較，應該和 5，int 比較，如果滿足則往左遞歸，root的值是6，這時候6比較的是5,7它應該介于5，7之間…

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        def juedge(left,root,right):
            if not root:
                return True
            if left<root.val<right:
                return juedge(left,root.left,root.val) and juedge(root.val,root.right,right)
            else:
                return False
        return juedge(-float('INF'),root,float('INF'))
        # inf 代表正無窮，-inf 代表負無窮

3、對稱二叉樹

給定一個二叉樹，檢查它是否是鏡像對稱的。

例如，二叉樹 [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

思路：

(1)如果左子樹或右子樹有一個為空，則判斷兩個是否都為空，如果都為空則傳回 True,否則傳回 False

(2)如果兩個節點值不相等傳回 False,否則進行遞歸判斷

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return True
        def judeg(lroot,rroot):
            if not lroot or rroot:
                return lroot is rroot
            if lroot.val != rroot.val:
                return False
            return judeg(lroot.left,rroot.right) and judeg(lroot.right,rroot.left)
        return judeg(root.left,root.right)

方法二：

class Solution(object):
    def isSymmetric(self, root):
        def is_mirror(left, right):
            if not left and not right:
                return True
            if not left or not right:
                return False
            
            return left.val==right.val and is_mirror(left.left, right.right) and is_mirror(left.right, right.left)
        return not root or is_mirror(root.left, root.right)

4、左葉子之和

計算給定二叉樹的所有左葉子之和

在這個二叉樹中，有兩個左葉子，分别是 9 和 15，是以傳回 24

方法一：遞歸

def sumOfLeftLeaves(self, root: TreeNode) -> int:
        if not root:
            return 0
		# 判斷左子樹是否符合條件
        if root.left and not root.left.left and not root.left.right:
            return root.left.val + self.sumOfLeftLeaves(root.right)
        # 進行遞歸
        return self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)

方法二：非遞歸

用一個隊列對二叉樹進行層序周遊，如果是左子樹的葉子節點，則加入傳回變量中

int sumOfLeftLeaves(TreeNode* root) {
        queue<TreeNode*>q;
        if(root == nullptr){
            return 0;
        }
        q.push(root);
        int ans = 0;
        while(!q.empty()){
            TreeNode* temp = q.front();
            q.pop();
            if(temp->left && temp->left->left == nullptr 
                && temp->left->right == nullptr){

                ans+=temp->left->val;
            }
            if(temp->left){
                q.push(temp->left);
            }
            if(temp->right){
                q.push(temp->right);
            }
        }
        return ans;
    }

5、二叉樹的右視圖

給定一棵二叉樹，想象自己站在它的右側，按照從頂部到底部的順序，傳回從右側所能看到的節點值

示例

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

輸出: [1, 3, 4]

思路：其實就是個層次周遊，然後把每層的最後一個節點附加到傳回清單中。

def rightSideView(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        temp = [root]
        res = []
        while temp:
            res.append(temp[-1].val)
            temp = [kid for node in temp for kid in [node.left,node.right]if kid]
        return res

C++版本

vector<int> rightSideView(TreeNode* root) {
        vector<int>res;
        if(!root){
            return res;
        }
        queue<TreeNode*>q;
        q.push(root);
        while (!q.empty()){
            int size = q.size();
            res.push_back(q.front()->val);
            while (size--){
                TreeNode* temp = q.front();
                q.pop();
                if (temp->right){
                    q.push(temp->right);
                }
                if (temp->left){
                    q.push(temp->left);
                }
            }
        }
        return res;
    }

6、序列化二叉樹

請實作兩個函數，分别用來序列化和反序列化二叉樹

二叉樹的序列化是指：把一棵二叉樹按照某種周遊方式的結果以某種格式儲存為字元串，進而使得記憶體中建立起來的二叉樹可以持久儲存。序列化可以基于先序、中序、後序、層序的二叉樹周遊方式來進行修改，序列化的結果是一個字元串，序列化時通過某種符号表示空節點（#），以！表示一個結點值的結束(value!)

二叉樹的反序列化是指：根據某種周遊順序得到的序列化字元串結果str，重構二叉樹

class Solution {
public:
    char* Serialize(TreeNode *root) {    
        buf.clear();
        SerializePre(root);
        int size = buf.size();
        int* res = new int[size];
        for(int i = 0;i < size;++i){
            res[i] = buf[i];
        }
        return (char*)res;
    }
    TreeNode* Deserialize(char *str) {
        int* p = (int*)str;
        return DeserializePre(p);
    }
private:
    // 進行前序周遊,序列化二叉樹
    void SerializePre(TreeNode *root){
        if(root == nullptr){
            buf.push_back(0xFFFFFFFF);
        }else{
            buf.push_back(root->val);
            SerializePre(root->left);
            SerializePre(root->right);
        }
    }
    // 反序列化二叉樹
    TreeNode* DeserializePre(int* &p){
        if(*p == 0xFFFFFFFF){
            p++;
            return nullptr;
        }
        TreeNode* res = new TreeNode(*p);
        p++;
        res->left = DeserializePre(p);
        res->right = DeserializePre(p);
        return res;
    }
private:
    vector<int>buf;
};

7、二叉樹路徑總和

給定一個二叉樹和一個目标和，判斷該樹中是否存在根節點到葉子節點的路徑，這條路徑上所有節點值相加等于目标和

說明: 葉子節點是指沒有子節點的節點。

示例：給定如下二叉樹，以及目标和 sum = 22

5
         / \
        4   8
       /   / \
      11  13  4
     /  \      \
    7    2      1

思路：由于是從根節點到葉子節點，是以判定條件是

if not root.left and not root.right and if root.val == target:

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(root == nullptr){
            return false;
        }
        if(root->val == sum && root->left == nullptr && root->right == nullptr){
            return true;
        }
        return hasPathSum(root->left,sum-root->val) ||
        hasPathSum(root->right,sum - root->val);
    }
};

進階

給定一個二叉樹和一個目标和，找到所有從根節點到葉子節點路徑總和等于給定目标和的路徑。

說明: 葉子節點是指沒有子節點的節點。

示例

給定如下二叉樹，以及目标和 sum = 22

5
         / \
        4   8
       /   / \
      11  13  4
     /  \    / \
    7    2  5   1

傳回：

[

[5,4,11,2],

[5,8,4,5]

]

思路還是和上一題大緻相同，參數多加了一個路徑 path

class Solution {
public:
    vector<vector<int>>ans;
    vector<int>tmp;
    void dfs(TreeNode* root,int sum){
        if(root == nullptr) return;
        tmp.push_back(root->val);
        if(root->val == sum && root->left == nullptr &&\
        	root->right == nullptr){
            ans.push_back(tmp);
        }
        dfs(root->left,sum-root->val);
        dfs(root->right,sum-root->val);
        tmp.pop_back();
    }
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        dfs(root,sum);
        return ans;
    }
};

8、求根到葉子節點數字之和

給定一個二叉樹，它的每個結點都存放一個 0-9 的數字，每條從根到葉子節點的路徑都代表一個數字。

例如，從根到葉子節點路徑 1->2->3 代表數字 123。

計算從根到葉子節點生成的所有數字之和。

說明: 葉子節點是指沒有子節點的節點。

示例1

輸入: [1,2,3]
  1
 / \
2   3
輸出: 25

解釋:

從根到葉子節點路徑 1->2 代表數字 12.

從根到葉子節點路徑 1->3 代表數字 13.

是以，數字總和 = 12 + 13 = 25.

示例2

輸入: [4,9,0,5,1]
    4
   / \  
  9   0
 / \
5   1
輸出: 1026

解釋:

從根到葉子節點路徑 4->9->5 代表數字 495.

從根到葉子節點路徑 4->9->1 代表數字 491.

從根到葉子節點路徑 4->0 代表數字 40.

是以，數字總和 = 495 + 491 + 40 = 1026.

class Solution {
public:
    int sum = 0;
    void clac(TreeNode* root,int num){
        if(root->left == nullptr && root->right == nullptr){
            sum += num*10 + root->val;
        }
        if(root->left){
            clac(root->left,num*10+root->val);
        }
        if(root->right){
            clac(root->right,num * 10+root->val);
        }
    }
    int sumNumbers(TreeNode* root) {
        if(root == nullptr){
            return 0;
        }
        clac(root,0);
        return sum;
    }
};

9、最小高度樹

給定一個有序整數數組，元素各不相同且按升序排列，編寫一個算法，建立一棵高度最小的二叉搜尋樹。

示例:

給定有序數組: [-10,-3,0,5,9],

一個可能的答案是：[0,-3,9,-10,null,5]

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if(nums.size() == 0){
            return nullptr;
        }
        int mid = nums.size()/2;
        TreeNode* root = new TreeNode(nums[mid]);
        vector<int>left(nums.begin(),nums.end()-(nums.size()-mid));
        vector<int>right(nums.begin()+mid+1,nums.end());
        root->left = sortedArrayToBST(left);
        root->right = sortedArrayToBST(right);
        return root;
    }
};

頻率很高的手寫代碼面試題--二叉樹類型(下)

頻率很高的面試題--二叉樹類型

1、相同的樹

2、驗證二叉搜尋樹

3、對稱二叉樹

4、左葉子之和

5、二叉樹的右視圖

6、序列化二叉樹

7、二叉樹路徑總和

8、求根到葉子節點數字之和

9、最小高度樹

繼續閱讀

劍指offer 對稱二叉樹1.題目描述2.分析

劍指offer（61）：對稱的二叉樹

計算日期到天數轉換,幸運的袋子

對稱二叉樹(力扣習題)

另類加法,允許增加子函數

C++ 程式設計題/簡單錯誤記錄,合唱團，馬戲團

劍指offer的Python實作之二叉樹(2)：相同的樹相同的樹及其相關題目

404. 左葉子之和左葉子之和

一組資料中隻有一個數字出現了一次。其他所有數字都是成對出現的。

[LeetCode] 101.對稱二叉樹

199. 二叉樹的右視圖二叉樹的右視圖

Leetcode:199.二叉樹的右視圖

驗證二叉搜尋樹的兩種思路及JAVA代碼實作

對稱二叉樹對稱二叉樹

LeetCode 98.Validate Binary Search Tree (驗證二叉搜尋樹)

實作一個函數，可以左旋字元串中的k個字元

頻率很高的手寫代碼面試題--二叉樹類型(下)

頻率很高的面試題--二叉樹類型

1、相同的樹

2、驗證二叉搜尋樹

3、對稱二叉樹

4、左葉子之和

5、二叉樹的右視圖

6、序列化二叉樹

7、 二叉樹路徑總和

8、求根到葉子節點數字之和

9、 最小高度樹

繼續閱讀

7、二叉樹路徑總和

9、最小高度樹