二叉树算法的框架套路总结

总结

本文主要来源于Leetcode用户：https://leetcode.cn/u/labuladong/，感谢写了这么好的文章

作者：labuladong
链接：https://leetcode.cn/problems/same-tree/solutions/6558/xie-shu-suan-fa-de-tao-lu-kuang-jia-by-wei-lai-bu-/

二叉树的设计总路线：明确一个节点要做什么事情，然后剩下的事情交给框架

void traverse(TreeNode root){
    // root需要做的事情


    // 遍历所要做的事情 全部在这里
    traverse(root.left);
    traverse(root.right);
}

将所有的节点值加一

void plusOne(TreeNode root){
    if(root == null){
        return ;// 首先写出递归结束条件
    }

    root.val += 1;
    plusOne(root.left);
    plueOne(root.right);
}

如何判断两个二叉树是否相等

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 比较两棵树是否相等
        // 深度优先遍历

        // 当两个节点都是null的时候 返回true  递归出口
        if(p == null && q == null){
            return true;
        }else if(p ==null || q == null){
            return false;
        }else if(p.val != q.val){
            return false;
        }


        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
        
    }
}

判断二叉搜索树

下面是错误的代码示例，因为判断一棵树是不是二叉搜索树，需要判断当前节点是不是大于全部的左子树节点以及小于全部的右子树节点，下面的代码只判断了左右节点

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 >= root.right.val) return false;

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

正确的代码

boolean isValidBST(TreeNode root) {
    return isValidBST(root, null, null);
}

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

二叉搜索树插入一个节点

找到插入位置，然后进行插入操作

TreeNode insertIntoBST(TreeNode root,int val){
    // 找到空位置插入新节点
    if(root == null){
        return new TreeNode(val);
    }

    if(root.val < val){
        root.right = insertIntoBST(root.right,val);
    }

    if(root.val > val){
        root.left = insertIntoBST(root.left,val);
    }


    return root;
}

二叉搜索树删除一个节点

首先搭建一个框架

TreeNode deleteNode(TreeNode root,int key){
    if(root.val == key){
        // 删除操作
    }else if(root.val > key){
        root.left = deleteNode(root.left,key);
    }else if(root.val < key){
        root.right = deleteNode(root.right,key);
    }

    return root;
}

如果是null 直接return null

if(root.left == null && root.right == null)
{
    return null;
}

如果当前节点只有一个非空节点，让这个非空节点代替他

if(root.left == null){
    return root.right;
}

if(root.right == null){
    return root.left;
}

如果当前节点有两个子节点找到右子树的最小节点代替自己

if(root.left != null && root.right != null){
    // 找到右子树的最小节点
    TreeNode minNode = getMin(root.right);

    // 将root更换
    root.val = minNode.val;

    // 删除minNode
    root.right = deleteNode(root.right,minNode.val);
}

总结代码


TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) return null;
    if (root.val == key) {
        // 这两个 if 把情况 1 和 2 都正确处理了
        if (root.left == null) return root.right;
        if (root.right == null) return root.left;
        // 处理情况 3
        TreeNode minNode = getMin(root.right);
        root.val = minNode.val;
        root.right = deleteNode(root.right, minNode.val);
    } else if (root.val > key) {
        root.left = deleteNode(root.left, key);
    } else if (root.val < key) {
        root.right = deleteNode(root.right, key);
    }
    return root;
}

TreeNode getMin(TreeNode node) {
    // BST 最左边的就是最小的
    while (node.left != null) node = node.left;
    return node;
}