树

树

树是一种数据结构。为什么会有树这种数据结构？目前理解的非常不深，回答不上来，在以后的日子里补。

判断平衡二叉树

什么是平衡？任意一个节点，其两棵子树的高度差不超过 1。

object Solution {
    def isBalanced(root: TreeNode): Boolean = {
        if (root == null) {
            return true
        }
        var abs = Math.abs(getDepth(root.left) - getDepth(root.right))
        if (abs <= 1 && isBalanced(root.left) && isBalanced(root.right)){
            return true
        }
        return false

    }
    
    def getDepth(root:TreeNode): Int = {
        if (root==null) {
            return 0
        }
        var left = getDepth(root.left)
        var right = getDepth(root.right)
        return Math.max(left, right) + 1
        
    }
}

判断是否二叉搜索树

本质上就是树的遍历，这里比较粗暴，二叉搜索树的中序遍历肯定是一个递增序列，如果不是递增序列，就不是二叉搜索树

object Solution {
    
    var seq = Seq[Int]()
    
    def inOrder(root: TreeNode):Unit = {
        if(root != null) {
            inOrder(root.left)
            seq = seq :+ root.value
            inOrder(root.right)
        }
    }
    
    def isValidBST(root: TreeNode): Boolean = {
        
        inOrder(root)
        if (seq.length == 0){
            return true
        }
        if (seq.length == 1){
            return true
        }
        for (i <- 0 until seq.length-1) {
            if (seq(i) >= seq(i+1)){
                return false
            }
        }
        return true 
        

    }
}

二叉搜索树的下一个结点

遍历元素放入列表，查找列表。

class Solution:
    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:
        if root:
            if p.val >= root.val:
                return self.inorderSuccessor(root.right,p)
            else:
            	a = self.inorderSuccessor(root.left,p)
                if a is None:
                    return root
                else:
                    return a
        return None