LeetCode.965-單一二叉樹(Univalued Binary Tree)

這是悅樂書的第366次更新，第394篇原創

01 看題和準備

今天介紹的是

LeetCode

算法題中

Easy

級别的第

228

題（順位題号是

965

）。如果樹中的每個節點具有相同的值，則二叉樹是單一的。當且僅當給定樹是單一時才傳回

true

。

1
   / \   
  1   1
 / \   \
1   1   1
           

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

輸出: true

2
   / \   
  2   2
 / \   
5   2   
           

輸入: [2,2,2,5,2]

輸出: false

注意：

• 給定樹中的節點數量将在[1,100]範圍内。
• 每個節點的值将是[0,99]範圍内的整數。

02 第一種解法

題目的意思是判斷二叉樹中的節點值是否都是一個值，為同一個值就傳回

true

，不是就傳回

false

思路：使用遞歸，中序周遊二叉樹的每個節點，存入

List

中，再周遊比較

List

中的元素是否都等于二叉樹的根節點值。

public boolean isUnivalTree(TreeNode root) {
    List<Integer> list = new ArrayList<Integer>();
    helper(root, list);
    for (Integer num : list) {
        if (num != root.val) {
            return false;
        }
    }
    return true;
}

public void helper(TreeNode root, List<Integer> list) {
    if (root == null) {
        return ;
    }
    helper(root.left, list);
    list.add(root.val);
    helper(root.right, list);
}
           

03 第二種解法

針對第一種解法的遞歸方式，我們也可以換成疊代的方式，借助棧

Stack

來實作。

public boolean isUnivalTree2(TreeNode root) {
    List<Integer> list = new ArrayList<Integer>();
    Stack<TreeNode> stack = new Stack<TreeNode>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        list.add(node.val);
        if (node.left != null) {
            stack.push(node.left);
        }
        if (node.right != null) {
            stack.push(node.right);
        }
    }
    for (Integer num : list) {
        if (num != root.val) {
            return false;
        }
    }
    return true;
}
           

04 第三種解法

在第二種解法的基礎上，我們可以直接判斷出棧的樹的節點值是否等于根節點值，省掉存入

List

的步驟。

public boolean isUnivalTree3(TreeNode root) {
    Stack<TreeNode> stack = new Stack<TreeNode>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        if (node.val != root.val) {
            return false;
        }
        if (node.left != null) {
            stack.push(node.left);
        }
        if (node.right != null) {
            stack.push(node.right);
        }
    }
    return true;
}
           

05 第四種解法

既然判斷節點值是否都是同一個值，那麼可以借助

HashSet

去重的特性，使用遞歸，中序周遊節點值，存入

HashSet

中，最後判斷

HashSet

的

size

是否等于1即可。

public boolean isUnivalTree4(TreeNode root) {
    Set<Integer> set = new HashSet<Integer>();
    helper(root, set);
    return set.size() == 1;
}

public void helper(TreeNode root, Set<Integer> set) {
    if (root == null) {
        return ;
    }
    helper(root.left, set);
    set.add(root.val);
    helper(root.right, set);
}
           

06 第五種解法

針對第四種解法，也可以通過疊代的方式的來實作，借助棧

Stack

public boolean isUnivalTree5(TreeNode root) {
    Set<Integer> set = new HashSet<Integer>();
    Stack<TreeNode> stack = new Stack<TreeNode>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        set.add(node.val);
        if (node.left != null) {
            stack.push(node.left);
        }
        if (node.right != null) {
            stack.push(node.right);
        }
    }
    return set.size() == 1;
}
           

07 第六種解法

我們也可以直接用遞歸，不借助其他的類。

public boolean isUnivalTree6(TreeNode root) {
    return help(root, root.val);            
}

public boolean help(TreeNode root, int num){
    if (root != null && root.left == null 
            && root.right == null && root.val == num) {
        return true;
    }
    if (root != null && root.left == null) {
        return root.val == num && help(root.right, num);
    }  
    if (root != null && root.right == null) {
        return root.val == num && help(root.left, num);
    }
    return root != null && root.val == num 
            && help(root.right, num) && help(root.left, num);
}
           

08 第七種解法

針對上面的第六種解法，我們還可以再簡化下。因為題目給了二叉樹節點的數量範圍，

root

是不會為空的，等于

null

表示目前沒有繼續可以向下周遊的節點了。

public boolean isUnivalTree7(TreeNode root) {
    return helper(root, root.val);            
}

public boolean helper(TreeNode root, int num){
    if (root == null) {
        return true;
    }
    if (root.val != num) {
        return false;
    }
    return helper(root.right, num) && helper(root.left, num);
}
           

09 小結

算法專題目前已連續日更超過七個月，算法題文章234+篇，公衆号對話框回複【資料結構與算法】、【算法】、【資料結構】中的任一關鍵詞，擷取系列文章合集。

以上就是全部内容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！