【二叉树】根据描述创建二叉树

0x00 题目

给你一个二维整数数组 ​

​descriptions​

​​ 其中 ​

​descriptions[i] = [parenti, childi, isLefti]​

​ 表示

​

​parenti​

​ 是 ​

​childi​

​ 在 二叉树 中的 ​

​父节点​

​ 二叉树中各节点的值 互不相同

此外：

如果 ​​

​isLefti == 1​

​​ ，那么 ​

​childi​

​​ 就是 ​

​parenti​

​​ 的​

​左​

​​子节点

如果 ​​

​isLefti == 0​

​​ ，那么 ​

​childi​

​​ 就是 ​

​parenti​

​​ 的​

​右​

​​子节点

请你根据 descriptions 的描述来构造二叉树并返回其 根节点

0x01 思路

根据所给的数据

创建​​

​节点​

​​与​

​父节点​

​​ 再通过一个​

​字典​

​保存对应的

节点与其父节点

最后再判断那个​

​不存在​

​父节点的节点

就是​

​根​

​节点

0x02 解法

语言：​

​Swift​

​

树节点：​

​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
    }
}      

func createBinaryTree(_ descriptions: [[Int]]) -> TreeNode? {
    if descriptions.isEmpty { return nil }
    
    // 值对应的节点
    var dic: [Int:TreeNode] = [:]
    // 值对应的父节点
    var per: [Int:TreeNode] = [:]
    // 那些父节点的值
    var arr: [Int] = []
    
    for i in 0..<descriptions.count {
        let t = descriptions[i]
        let p = t[0]
        let c = t[1]
        let isLeft = t[2]
        
        // 取出父节点和子节点
        var pNode = dic[p]
        var cNode = dic[c]
        
        // 不存在就创建
        if pNode == nil {
            pNode = TreeNode(p)
            dic[p] = pNode
            // 添加到数组
            arr.append(p)
        }
        if cNode == nil {
            cNode = TreeNode(c)
            dic[c] = cNode
        }
        
        // 值对应的父节点
        per[c] = pNode
        
        if isLeft == 1 {
            pNode!.left = cNode
        }else{
            pNode!.right = cNode
        }
    }
    
    var root: TreeNode? = nil
    // 从可能的父节点中寻找，没有父节点的，就是根节点
    for i in 0..<arr.count {
        let val = arr[i]
        if per[val] == nil {
            root = dic[val]
        }
    }
    
    return root
}
      

0x03 我的小作品