当前位置：网站首页>[binary tree] verify binary tree

[binary tree] verify binary tree

2022-07-22 08:06:00 【How cold it is】

0x00 subject

There are... On the binary tree n Nodes , Press from 0 To n - 1 Number
Where nodes i The two child nodes of are leftChild[i] and rightChild[i]

Only all Nodes can form and only formation One Efficient binary tree
return true; Otherwise return to false

If node i There is no left child node , that leftChild[i] Is equal to -1
The right child node also complies with this rule

Be careful ： Node has no value , Only node numbers are used in this problem

0x01 Ideas

First of all, find root node
And then again Traverse
Check if there is Ring

0x02 solution

Language ：Swift

Tree node ：TreeNode

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}

solution ：

func validateBinaryTreeNodes(_ n: Int, _ leftChild: [Int], _ rightChild: [Int]) -> Bool {
    //  Traverse  2  An array , Count the number of times 
    var arr = [Int](repeating: 0, count: n)
    for i in 0..<n {
        let left = leftChild[i]
        if left != -1 {
            arr[left] += 1
        }
        let right = rightChild[i]
        if right != -1 {
            arr[right] += 1
        }
    }
    
    //  Find the root node 
    var root = -1
    for i in 0..<n {
        if arr[i] == 0 {
            root = i
            break
        }
    }
    if root == -1 {
        return false
    }
    
    //  Traverse , Check whether there are rings ( A node is accessed many times )
    var count = 0
    var queue: [Int] = []
    var visited = [Int](repeating: 0, count: n)
    queue.append(root)
    visited[root] += 1
    
    while !queue.isEmpty {
        let node = queue.removeFirst()
        count += 1
        
        let left = leftChild[node]
        if left != -1 {
            visited[left] += 1
            if visited[left] > 1 {
                return false
            }
            queue.append(left)
        }
        
        let right = rightChild[node]
        if right != -1 {
            visited[right] += 1
            if visited[right] > 1 {
                return false
            }
            queue.append(right)
        }
    }
    
    //  Each node should traverse to 
    return count == n
}