總結:二叉樹的屬性

語言: CN / TW / HK

theme: channing-cyan

持續創作,加速成長!這是我參與「掘金日新計劃 · 10 月更文挑戰」的第12天,點選檢視活動詳情

是否對稱

給定一個二叉樹,檢查它是否是映象對稱的。

image

上圖為對稱二叉樹

image

上圖的二叉樹則不是映象的

思路

判斷是否是映象,需要去判斷二叉樹的裡側和外側是否相同。

這就需要去判斷根節點下左子樹與右子樹裡側和外側是否相等。比較的方法是拿左子樹的 “左-右-中” 節點和右子樹的“右-左-中”為順序的節點做比較。

這題用遞迴的方式解比較方便,遞迴的思路如下: 1. 因為要比較倆個子樹是否是映象的,所以遞迴的引數為倆個,分別是左子樹節點和右子樹節點 2. 終止條件有三個:

  • 左節點為空,右節點不為空,返回 false,左節點不為空,右節點為空,返回 false;
  • 左右節點均不為空,但數值不同,返回 false;
  • 如果左右節點均為空,則返回 true;

  • 如果以上條件均不滿足,則再進入遞迴邏輯

程式碼實現

``` public boolean isSymmetric1(TreeNode root) { return compare(root.left, root.right); }

private boolean compare(TreeNode left, TreeNode right) {

    if (left == null && right != null) {
        return false;
    }
    if (left != null && right == null) {
        return false;
    }

    if (left == null && right == null) {
        return true;
    }
    if (left.val != right.val) {
        return false;
    }
    // 比較外側
    boolean compareOutside = compare(left.left, right.right);
    // 比較內側
    boolean compareInside = compare(left.right, right.left);
    return compareOutside && compareInside;
}

```

時間複雜度:O(N),其中 N 是樹的節點數。對每個節點訪問一次。

空間複雜度:O(H),其中 H 是樹的高度

二叉樹的最大深度

給定一個二叉樹,找出其最大深度。

思路

二叉樹的深度是指根節點到最遠葉子節點的最長路徑上的節點數。

我們可以通過遞迴的方式求解此題:

  1. 遞迴函式的傳入的引數為二叉樹的根節點,返回值為二叉樹的高度;
  2. 遞迴的終止條件為當節點為空節點時,返回高度為 0;
  3. 先求出它左子樹的高度,然後再求出它右子樹的高度,倆高度的最大值+1為二叉樹的最大深度。

程式碼如下:

java class solution { public: int getdepth(treenode node) { if (node == null) return 0; int leftdepth = getdepth(node.left); // 左 int rightdepth = getdepth(node.right); // 右 int depth = 1 + Math.max(leftdepth, rightdepth); // 中 return depth; } int maxdepth(treenode root) { return getdepth(root); } };

時間複雜度:O(N),其中 N 是樹的節點數。對每個節點訪問一次。

空間複雜度:O(H),其中 H 是樹的高度

同理,該方法適用於求 N 叉樹的最大深度,程式碼如下:

```java // Definition for a Node. class Node { public int val; public List children;

public Node() {}

public Node(int _val) {
    val = _val;
}

public Node(int _val, List<Node> _children) {
    val = _val;
    children = _children;
}

};

class Solution { public int maxDepth(Node root) { if (root == null) { return 0; } else if (root.children.isEmpty()) { return 1;
} else { List heights = new LinkedList<>(); // 迴圈求出每個子樹的高度 for (Node item : root.children) { heights.add(maxDepth(item)); } return Collections.max(heights) + 1; } } }

```

時間複雜度:O(N),其中 N 是樹的節點數。對每個節點訪問一次。

空間複雜度:O(H),其中 H 是樹的高度

二叉樹的最小深度

說明:最小深度是從根節點到最近葉子節點的最短路徑上的節點數量。

這裡有個誤區需要解釋一下,是從根節點到最近的葉子節點,如果根節點沒有左子樹或者右子樹,很多人就覺得最小深度為 1,這是不對的。是從根節點到最近葉子節點的最短路徑上的節點數量才是最小深度。

可以看出, 求二叉樹的最小深度和求二叉樹的最大深度的差別主要在於處理左右孩子不為空的邏輯。

程式碼如下:

java class Solution { /** * 遞迴法,相比求MaxDepth要複雜點 * 因為最小深度是從根節點到最近**葉子節點**的最短路徑上的節點數量 */ public int minDepth(TreeNode root) { if (root == null) { return 0; } int leftDepth = minDepth(root.left); int rightDepth = minDepth(root.right); if (root.left == null) { return rightDepth + 1; } if (root.right == null) { return leftDepth + 1; } // 左右結點都不為null return Math.min(leftDepth, rightDepth) + 1; } }

時間複雜度:O(N),其中 N 是樹的節點數。對每個節點訪問一次。

空間複雜度:O(H),其中 H 是樹的高度。

求二叉樹有多少個節點

給出一個完全二叉樹,求出該樹的節點個數。

此題可用求二叉樹的最大深度的方式來求出,程式碼如下:

java class solution { public: int getdepth(treenode node) { if (node == null) return 0; int leftdepth = getdepth(node.left); // 左 int rightdepth = getdepth(node.right); // 右 int depth = 1 + leftdepth, rightdepth; // 中 return depth; } int maxdepth(treenode root) { return getdepth(root); } };

時間複雜度:O(n),n 為二叉樹節點個數 空間複雜度:O(h),h 為 樹的高度

平衡二叉樹

給定一個二叉樹,判斷它是否是高度平衡的二叉樹。

本題中,一棵高度平衡二叉樹定義為:一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過1。

思路

既然是要求比較高度,則我們可以用到後序遍歷的方式。

  1. 明確遞迴函式的引數和返回值,引數為傳入的根節點,如果左右子樹的返回值 > 1,則我們返回 -1,表示已經不是平衡二叉樹了;
  2. 遞迴的終止條件為遇到了空節點,則 return 0, 表示當前節點為 根節點,高度為 0;
  3. 單層遞迴邏輯為,分別求出左右子樹的高度,如果差值小於等於 1,則返回當前二叉樹的高度,否則返回 -1,表示已經不是二叉樹了;

程式碼如下:

``` class Solution { /* * 遞迴法 / public boolean isBalanced(TreeNode root) { return getHeight(root) != -1; }

private int getHeight(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int leftHeight = getHeight(root.left);
    if (leftHeight == -1) {
        return -1;
    }
    int rightHeight = getHeight(root.right);
    if (rightHeight == -1) {
        return -1;
    }
    // 左右子樹高度差大於1,return -1表示已經不是平衡樹了
    if (Math.abs(leftHeight - rightHeight) > 1) {
        return -1;
    }
    return Math.max(leftHeight, rightHeight) + 1;
}

} ```

二叉樹的所有路勁

給定一個二叉樹,返回所有從根節點到葉子節點的路徑。

思路

根據題意要從根節點到葉子節點的路徑,所以需要前序遍歷。

  1. 確定遞迴的引數和返回值,引數為傳入的根節點,記錄每條路徑的節點值陣列path,以及路徑結果陣列res;
  2. 當遇到葉子節點的時候終止,並將路徑節點值數組裡的數值轉換成字串,然後加入到結果陣列;
  3. 遞迴的單層邏輯為,因為是前序遍歷:中-左-右,所以先處理中間節點,加入到 path 中,然後再遞迴處理左子樹和右子樹,並遞迴完後回溯;

程式碼如下:

``` //解法一 class Solution { /* * 遞迴法 / public List binaryTreePaths(TreeNode root) { List res = new ArrayList<>(); if (root == null) { return res; } List paths = new ArrayList<>(); traversal(root, paths, res); return res; }

private void traversal(TreeNode root, List<Integer> paths, List<String> res) {
    paths.add(root.val);
    // 葉子結點
    if (root.left == null && root.right == null) {
        // 輸出
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < paths.size() - 1; i++) {
            sb.append(paths.get(i)).append("->");
        }
        sb.append(paths.get(paths.size() - 1));
        res.add(sb.toString());
        return;
    }
    if (root.left != null) {
        traversal(root.left, paths, res);
        paths.remove(paths.size() - 1);// 回溯
    }
    if (root.right != null) {
        traversal(root.right, paths, res);
        paths.remove(paths.size() - 1);// 回溯
    }
}

} ```

左葉子之和

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

思路

首先要判斷這棵二叉樹有沒有左葉子,就必須要通過節點的父節點來判斷其左孩子是不是左葉子,判斷程式碼如下:

if (root.left != null && root.left.left == null && root.left.right == null) { // 中 midValue = root.left.val; }

用後序遍歷找出所有的左葉子節點數值之和,遞迴方式如下: 1. 遞迴函式的傳參為根節點,返回值為左葉子節點之和; 2. 遞迴終止條件為 root == null 返回 0; 3. 單層遞迴邏輯:當遇到左葉子節點的時候,記錄數值,然後通過遞迴求取左子樹左葉子之和,和 右子樹左葉子之和,相加便是整個樹的左葉子之和;

程式碼如下:

``` class Solution { public int sumOfLeftLeaves(TreeNode root) { if (root == null) return 0; int leftValue = sumOfLeftLeaves(root.left); // 左 int rightValue = sumOfLeftLeaves(root.right); // 右

    int midValue = 0;
    if (root.left != null && root.left.left == null && root.left.right == null) { // 中
        midValue = root.left.val;
    }
    int sum = midValue + leftValue + rightValue;
    return sum;
}

} ```

左下角的值

給定一個二叉樹,在樹的最後一行找到最左邊的值。

思路

本題比較容易下手的解題方式可以用層序遍歷的方法,找到最後一行的最左邊。

但是也可以用遞迴法來實現,首先可以明確深度最大的葉子節點一定是最後一行,那如何找最左邊的呢?我們可以使用前序遍歷,優先從左邊開始搜尋。

  1. 明確遞迴函式的引數和返回值:引數為傳入的根節點,以及一個int型變數用來記錄最長深度。返回值為 void;
  2. 當遇到葉子節點的時候,為終止條件,並開始統計最大深度;
  3. 確定單層遞迴邏輯,當不是葉子節點時,則繼續遍歷左子樹和右子樹,並記得要回溯;

程式碼如下:

```java // 遞迴法 class Solution { private int Deep = -1; private int value = 0; public int findBottomLeftValue(TreeNode root) { value = root.val; findLeftValue(root,0); return value; }

private void findLeftValue (TreeNode root,int deep) {
    if (root == null) return;
    if (root.left == null && root.right == null) {
        if (deep > Deep) {
            value = root.val;
            Deep = deep;
        }
    }
    if (root.left != null) findLeftValue(root.left,deep + 1);
    if (root.right != null) findLeftValue(root.right,deep + 1);
}

} ```

路勁總和 1

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

思路

利用遞迴來解答此題:

  1. 確定遞迴函式的傳參和返回值:引數為傳入的根節點和計數變數,該計數變數每次遞迴的時候需要減去當前節點的值,最後遇到葉子節點的時候判斷該葉子節點的值是否與它一致,如果一致,則表示找到了該路徑。返回值為bool型別;
  2. 遞迴函式的終止條件為:當遇到葉子節點的時候,並且計數變數等於葉子節點的值就返回 true;
  3. 單層遞迴邏輯為:遍歷左子樹和右子樹,並回溯

程式碼如下:

```java class solution { public boolean haspathsum(treenode root, int targetsum) { if (root == null) { return false; } targetsum -= root.val; // 葉子結點 if (root.left == null && root.right == null) { return targetsum == 0; } if (root.left != null) { boolean left = haspathsum(root.left, targetsum); if (left) {// 已經找到 return true; } } if (root.right != null) { boolean right = haspathsum(root.right, targetsum); if (right) {// 已經找到 return true; } } return false; } }

// 精簡後的程式碼

class solution { public boolean haspathsum(treenode root, int targetsum) {

    if (root == null) return false; // 為空退出

    // 葉子節點判斷是否符合
    if (root.left == null && root.right == null) return root.val == targetsum;

    // 求兩側分支的路徑和
    return haspathsum(root.left, targetsum - root.val) || haspathsum(root.right, targetsum - root.val);
}

} ```

路徑總和2

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

思路

解題思路與上一題相似,只是需要記錄路徑。

程式碼如下:

```java class solution { public list> pathsum(treenode root, int targetsum) { list> res = new arraylist<>(); if (root == null) return res; // 非空判斷

    list<integer> path = new linkedlist<>();
    preorderdfs(root, targetsum, res, path);
    return res;
}

public void preorderdfs(treenode root, int targetsum, list<list<integer>> res, list<integer> path) {
    path.add(root.val);
    // 遇到了葉子節點
    if (root.left == null && root.right == null) {
        // 找到了和為 targetsum 的路徑
        if (targetsum - root.val == 0) {
            res.add(new arraylist<>(path));
        }
        return; // 如果和不為 targetsum,返回
    }

    if (root.left != null) {
        preorderdfs(root.left, targetsum - root.val, res, path);
        path.remove(path.size() - 1); // 回溯
    }
    if (root.right != null) {
        preorderdfs(root.right, targetsum - root.val, res, path);
        path.remove(path.size() - 1); // 回溯
    }
}

} ```

我是傑少,如果您覺的我寫的不錯,那請給我 點贊+評論+收藏 後再走哦!

往期文章:

請你喝杯 ☕️ 點贊 + 關注哦~

  1. 閱讀完記得給我點個贊哦,有👍 有動力
  2. 關注公眾號--- HelloWorld傑少,第一時間推送新姿勢

最後,創作不易,如果對大家有所幫助,希望大家點贊支援,有什麼問題也可以在評論區裡討論😄~**