iT邦幫忙

第 12 屆 iThome 鐵人賽
DAY 16
0
Software Development

你總是躲不掉的，不如放膽面對 LeetCode 吧！系列 第 16 篇

Day 16: Tree - Binary Tree(2)

12th鐵人賽
1975 瀏覽

  • 分享至 

  • xImage
    •  

延續昨天的內容，今天講解如何新增、移除資料。

執行新增、移除前，需要什麼？

先想像一個動態 Array，假設要新增、移除一個資料在：

  • 特定的 index
  • 第一個數字小於某某數

這時候需要的是 Search，找到符合條件的項目後才開始進行新增、移除。將這個觀念移轉到 Tree 也是一樣的道理，不論是新增還是移除，首先需要的仍然是 Search，而 Tree 的 Search 則是昨天最後提到的 Traversal。

Traversal 有三種，那使用時機呢？在 Stack Overflow上有討論：

  • Inorder: 將使 Tree 如一維數列般，一個一個顯示項目。
  • Preorder: 如果想要優先取得 root 的項目，則適合使用。
  • Postorder: 如果想要優先取得 Leaf Node 的項目，則適合使用。

一般來說，習慣上使用 Inorder，讓 Tree 的 Search 如同 Array、Linked List 使用 Linear Search 般，一個一個顯示節點的資料。

新增節點，Insertion

來源

用 JS 實作

class node {
  /**
   * @param {number} val
   * @param {node} left
   * @param {node} right
   */
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

/**
 * @param {node} temp
 */
const inorder = (temp) => {
  if (temp === null) {
    return;
  }

  inorder(temp.left);
  console.log(temp.val);
  inorder(temp.right);
};

/**
 * @param {node} temp
 * @param {number} key
 */
const insert = (temp, key) => {
  if (temp === null) {
    temp = new node(key);
    return;
  }

  /**
   * @type {node[]};
   */
  let q = [];
  q.push(temp);

  while (q.length > 0) {
    temp = q[0];
    q.pop();

    if (temp.left === null) {
      temp.left = new node(key);
      break;
    } else {
      q.push(temp.left);
    }

    if (temp.right === null) {
      temp.right = new node(key);
      break;
    } else {
      q.push(temp.right);
    }
  }
};

let root = new node(10);
root.left = new node(11);
root.left.left = new node(7);
root.right = new node(9);
root.right.left = new node(15);
root.right.right = new node(8);

console.log("Inorder traversal before insertion:");
inorder(root);

let key = 12;
insert(root, key);

console.log("Inorder traversal after insertion:");
inorder(root);

用 Java 實作

import java.util.LinkedList;
import java.util.Queue;

public class BinaryTreeInsertion {
    static class Node {
        int key;
        Node left, right;

        Node(int key) {
            this.key = key;
            left = null;
            right = null;
        }
    }

    static Node root;
    static Node temp = root;

    static void inorder(Node temp) {
        if (temp == null) {
            return;
        }

        inorder(temp.left);
        System.out.print(temp.key + " ");
        inorder(temp.right);
    }

    static void insert(Node temp, int key) {
        if (temp == null) {
            root = new Node(key);
            return;
        }

        Queue<Node> q = new LinkedList<Node>();
        q.add(temp);

        while (!q.isEmpty()) {
            temp = q.peek();
            q.remove();

            if (temp.left == null) {
                temp.left = new Node(key);
                break;
            } else {
                q.add(temp.left);
            }

            if (temp.right == null) {
                temp.right = new Node(key);
                break;
            } else {
                q.add(temp.right);
            }
        }
    }

    public static void main(String[] args) {
        root = new Node(10);
        root.left = new Node(11);
        root.left.left = new Node(7);
        root.right = new Node(9);
        root.right.left = new Node(15);
        root.right.right = new Node(8);

        System.out.print("Inorder traversal before insertion:");
        inorder(root);

        int key = 12;
        insert(root, key);

        System.out.print("\nInorder traversal after insertion:");
        inorder(root);
    }
}

用 C 實作

#include <stdio.h>
#include <stdlib.h>

struct Node
{
    int val;
    struct Node *left;
    struct Node *right;
};

struct Node *new_node(int val)
{
    struct Node *node = (struct Node *)malloc(sizeof(struct Node));

    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return (node);
}

void inorder(struct Node *temp)
{
    if (temp != NULL)
    {
        inorder(temp->left);
        printf("%d", temp->val);
        inorder(temp->right);
    }
}

void insert(struct Node **tree, int key)
{

    struct Node *temp = NULL;

    if (!(*tree))
    {
        temp = (struct Node *)malloc(sizeof(struct Node));
        temp->val = key;
        temp->left = temp->right = NULL;
        *tree = temp;
        return;
    }

    if (key < (*tree)->val)
    {
        insert(&(*tree)->left, key);
    }
    else if (key > (*tree)->val)
    {
        insert(&(*tree)->right, key);
    }
}

int main(int argc, char const *argv[])
{
    struct Node *root = new_node(10);
    root->left = new_node(11);
    root->left->left = new_node(7);
    root->right = new_node(9);
    root->right->left = new_node(15);
    root->right->right = new_node(8);
    printf("Inorder traversal before insertion:");
    inorder(root);
    printf("\n");

    int key = 12;
    insert(&root, key);

    printf("Inorder traversal after insertion:");
    inorder(root);
    printf("\n");

    return 0;
}

刪除節點，Deletion

來源

用 JS 實作

class node {
  /**
   * @param {number} val
   * @param {node} left
   * @param {node} right
   */
  constructor(val){
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

/**
 * @param {node} temp
 */
const inorder = (temp) => {
  if (temp === null) {
    return;
  }

  inorder(temp.left);
  console.log(temp.val);
  inorder(temp.right);
};

/**
 * @param {node} root
 * @param {node} deepestNode
 */
const deleteDeepest = (root, deepestNode) => {
  /**
   * @type {node[]};
   */
  let q = [];
  q.push(root);

  while (q.length > 0) {
    let temp = q.pop();

    if (temp.val === deepestNode.val) {
      temp = null;
      return;
    }

    if (temp.left !== null) {
      if (temp.left.val === deepestNode.val) {
        temp.left = null;
        return;
      } else {
        q.push(temp.left);
      }
    }

    if (temp.right !== null) {
      if (temp.right.val === deepestNode.val) {
        temp.right = null;
        return;
      } else {
        q.push(temp.right);
      }
    }
  }
};

/**
 * @param {node} root
 * @param {number} key
 */
const deletion = (root, key) => {
  if (root === null) {
    return null;
  }

  if (root.left === null && root.right === null) {
    if (root.val == key) {
      return null;
    } else {
      return root;
    }
  }

  let keyNode= null;
  /**
   * @type {node[]};
   */
  let q = [];
  q.push(root);
  let temp;

  while (q.length > 0) {
    temp = q.pop();

    if (temp.val == key) {
      keyNode = temp;
    }

    if (temp.left !== null) {
      q.push(temp.left);
    }

    if (temp.right !== null) {
      q.push(temp.right);
    }
  }

  if (keyNode !== null) {
    let x = temp.val;
    deleteDeepest(root, temp);
    keyNode.val = x;
  }

  return root;
};

let root = new node(10);
root.left = new node(11);
root.left.left = new node(7);
root.left.right = new node(12);
root.right = new node(9);
root.right.left = new node(15);
root.right.right = new node(8);

console.log("Inorder traversal before deletion:");
inorder(root);

let key = 11;
root = deletion(root, key);

console.log("Inorder traversal after deletion:");
inorder(root);

用 Java 實作

import java.util.LinkedList;
import java.util.Queue;

class BinaryTreeDeletion {

    static class Node {
        int key;
        Node left, right;

        Node(int key) {
            this.key = key;
            left = null;
            right = null;
        }
    }

    static Node root;
    static Node temp = root;

    static void inorder(Node temp) {
        if (temp == null) {
            return;
        }

        inorder(temp.left);
        System.out.print(temp.key + " ");
        inorder(temp.right);
    }

    static void deleteDeepest(Node root, Node delNode) {
        Queue<Node> q = new LinkedList<Node>();
        q.add(root);

        Node temp = null;

        while (!q.isEmpty()) {
            temp = q.peek();
            q.remove();

            if (temp == delNode) {
                temp = null;
                return;
            }

            if (temp.right != null) {
                if (temp.right == delNode) {
                    temp.right = null;
                    return;
                } else {
                    q.add(temp.right);
                }
            }

            if (temp.left != null) {
                if (temp.left == delNode) {
                    temp.left = null;
                    return;
                } else {
                    q.add(temp.left);
                }
            }
        }
    }

    static void delete(Node root, int key) {
        if (root == null) {
            return;
        }

        if (root.left == null && root.right == null) {
            return;
        }

        Queue<Node> q = new LinkedList<Node>();
        q.add(root);
        Node temp = null, keyNode = null;

        while (!q.isEmpty()) {
            temp = q.peek();
            q.remove();

            if (temp.key == key) {
                keyNode = temp;
            }

            if (temp.left != null) {
                q.add(temp.left);
            }

            if (temp.right != null) {
                q.add(temp.right);
            }
        }

        if (keyNode != null) {
            int x = temp.key;
            deleteDeepest(root, temp);
            keyNode.key = x;
        }
    }

    public static void main(String[] args) {
        root = new Node(10);
        root.left = new Node(11);
        root.left.left = new Node(7);
        root.left.right = new Node(12);
        root.right = new Node(9);
        root.right.left = new Node(15);
        root.right.right = new Node(8);

        System.out.print("Inorder traversal before deletion:");
        inorder(root);

        int key = 11;
        delete(root, key);

        System.out.print("\nInorder traversal after deletion:");
        inorder(root);
    }
}

用 C 實作

目前還沒想到，先擱置。

刷題：100. Same Tree

題目

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:
Imgur

思考

這題只是很單純在比較 Tree 每個節點的值是否相同？是否都有子節點？

解題

用 JS 實作

/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
const isSameTree = (p, q) => {
  if (p === null && q === null) {
    return true;
  } else if (p === null || q === null) {
    return false;
  } else if (p.val === q.val) {
    return (isSameTree(p.left, q.left) && isSameTree(p.right, q.right));
  } else {
    return false;
  }
};

用 Java 實作

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null) {
            return false;
        } else if (p.val == q.val) {
            return (isSameTree(p.left, q.left) && isSameTree(p.right, q.right));
        } else {
            return false;
        }
    }
}

用 C 實作

bool isSameTree(struct TreeNode *p, struct TreeNode *q)
{
    if (p == NULL && q == NULL)
    {
        return true;
    }
    else if (p == NULL || q == NULL)
    {
        return false;
    }
    else if (p->val == q->val)
    {
        return (isSameTree(p->left, q->left) && isSameTree(p->right, q->right));
    }
    else
    {
        return false;
    }
}

看法

ㄜ，這題幾乎沒難度，只要稍微懂 Recursive 以及 Tree 的結構即可。

結論

Binary Tree 新增、刪除節點算是基本的運用，會這樣講是因為，只要調整新增節點時的選擇（左邊、右邊），就可以有更快速的 Search，這就是有名的 Binary Search Tree


上一篇
Day 15: Tree - Binary Tree(1)
下一篇
Day 17: Tree - Binary Tree - Binary Search Tree(BST)
系列文
你總是躲不掉的，不如放膽面對 LeetCode 吧！ 共 31 篇
  1. 27
    Day 27: Memoization
  2. 28
    Day 28: Divide and Conquer
  3. 29
    Day 29: Dynamic Programming, DP
  4. 30
    Day 30: Greedy Method
  5. 31
    完結心得
完整目錄
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言
iThome鐵人賽
參賽組數
1064 組
團體組數
40 組
累計文章數
22200 篇
完賽人數
602 人
iT+看影片追技術 看影片追技術 看更多
熱門tag 看更多
15th鐵人賽 16th鐵人賽 13th鐵人賽 14th鐵人賽 12th鐵人賽 11th鐵人賽 鐵人賽 2019鐵人賽 javascript 2018鐵人賽 python 2017鐵人賽 windows php c# windows server linux css react vue.js
熱門問題
熱門回答
熱門文章
IT邦幫忙