You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

965. 单值二叉树 - Univalued Binary Tree

. 1 min read

965. 单值二叉树 - Univalued Binary Tree

[Traversal of Tree]

如果二叉树每个节点都具有相同的值,那么该二叉树就是*单值*二叉树。
只有给定的树是单值二叉树时,才返回 `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

/**
 * 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

/**
 * 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);
    }
};

复杂度分析