1. 单值二叉树 - Univalued Binary Tree

965. 单值二叉树 - Univalued Binary Tree

[Traversal of Tree]

Problem Link

如果二叉树每个节点都具有相同的值,那么该二叉树就是*单值*二叉树。
只有给定的树是单值二叉树时,才返回 `true`;否则返回 `false`。

Example:

示例 1:

输入:[1,1,1,1,1,null,1]
输出:true

示例 2:

输入:[2,2,2,5,2]
输出:false

提示:

  1. 给定树的节点数范围是 [1, 100]
  2. 每个节点的值都是整数,范围为 [0, 99]

solution

My solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isUnivalTree(TreeNode root) {
        boolean result = preOrderByStack(root);
        return result;
    }

  	public boolean preOrderByStack(TreeNode root) {
        int value = root.val;
        boolean result = true;
  		Stack<TreeNode> stack = new Stack<TreeNode>();
  		TreeNode current = root;
  		while (current != null || !stack.isEmpty()) {
  			while (current != null) {
  				stack.push(current);
                if(current.val != value)
                    return false;
  				current = current.left;
  			}

  			if (!stack.isEmpty()) {
  				current = stack.pop();
  				current = current.right;
  			}
  		}
  		System.out.println();
        return true;
  	}
}

复杂度分析

Other Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool check(TreeNode* x, int v){
        if (x==NULL) return true;
        if (x->val!=v) return false;
        return check(x->left, v) && check(x->right, v);
        
    }
    bool isUnivalTree(TreeNode* root) {
        return check(root, root->val);
    }
};

复杂度分析