二叉树总结（一）

二叉树算法设计总路线

void traverse(TreeNode root) {
    // root TO DO

    traverse(root.left);
    traverse(root.right);
}

一些小坑

BST（二叉搜索树）的合法性

// 常见错法

boolean isValidBST(TreeNode root) {
    if(root == null) return true;
    if(root.left != null && root.val <= root.left.val) return false;
    if(root.right != null && root.val >= rot.right.val) return false;

    return isValidBST(root.left) && isValidBST(root.right);
}

BST要求整棵树的左边比右边小，而不是单颗树的左边比右边小

// 正确做法，增加参数列表加判断

boolean isValidBST(TreeNode root, TreeNode min, TreeNode max) {
    if(root == null) return true;
    if(min != null && root.val <= min.val) return false;
    if(max != null && root.val >= max.val) return false;

    return isValidBST(root.left, min, root) 
        && isValidBST(root.right, root, max);
}

面对复杂的二叉树元素，建议使用链表，修改指针可以避免出现错误

一些小技巧

continue updating