代码随想录[原文指路]

二叉树基础

1.种类

满二叉树
完全二叉树
二叉搜索树
平衡二叉搜索树AVL

2.存储方式

顺序存储
链式存储

3.遍历方式

深度优先(前中后序)
广度优先

递归三部曲

1.确定递归函数参数和返回值

确定哪些参数是递归的过程中需要处理的进而确定递归函数的参数
确定每次递归的返回值是什么进而确定递归函数的返回类型(相当于确定函数的作用)

2.确定终止条件

3.确定单层递归逻辑

确定每层递归需要处理的信息，清晰重复调用自己实现递归的过程
实际项目开发中要尽量避免递归！

遍历

1.前序

前中后序差不多，掌握一种
递归

public void preorder(TreeNode root,List<Integer> res){
    if(root==null) return;
    res.add(root.val);
    preorder(root.left,res);
    preorder(root.right,res);
}

迭代

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new LinkedList<>();
    Stack<TreeNode> st = new Stack<>();
    if(root!=null)st.push(root);
    //注意空节点不入栈
    while(!st.isEmpty()){
        TreeNode node = st.peek();
        if(node!=null){
            st.pop();//将当前节点弹出避免重复操作
            if(node.right!=null) st.push(node.right);//添加右节点
            if(node.left!=null) st.push(node.left);//添加左节点
            st.push(node);//添加中间节点
            st.push(null);//中节点访问过，但是还没有处理，加入空节点做为标记
        } else {//遇到空节点时将下一个节点放进结果集
            st.pop();//将空节点弹出
            node = st.peek();//取出空节点的下一个节点
            st.pop();//出栈
            result.add(node.val);//加入结果集
        }
    }
    return result;
}

2.层序

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> ress = new ArrayList();
    List<Integer> res;
    if(root==null) return ress;

    Queue<TreeNode> queue = new LinkedList();
    queue.offer(root);
    while(!queue.isEmpty()){
        res = new ArrayList();
        int size = queue.size();
        for(int i=0;i<size;i++){
            TreeNode node = queue.poll();
            res.add(node.val);
            if(node.left!=null) queue.offer(node.left);
            if(node.right!=null) queue.offer(node.right);
        }
        ress.add(res);
    }
    return ress;
}

3.遍历方式选择

二叉树的构造，无论普通二叉树还是二叉搜索树一定前序，都是先构造中节点
普通二叉树的属性，一般是后序，一般要通过递归函数的返回值做计算
二叉搜索树的属性，一定是中序

构造二叉树

//1.参数
一般为root，若通过数组构建则(nums,开始index,结束index)
//2.递归函数返回条件
if(xxx) return xxx;
//3.构建最大值为根节点
TreeNode root = new或其他操作;
//4.递归构建左右子树
root.left=digui(root.left);
root.right=digui(root.right);
//5.返回根节点
return root;

判断左右子树XXX

//1.参数
TreeNode p,TreeNode q
//2.递归函数返回条件
if(p==null && q==null) return true;
if(p==null || q==null || p.val!=q.val) return false;
//3.递归左右子树
boolean bool1=digui(要比较的两节点);
boolean bool2=digui(要比较的两节点);
//4.返回，若都要满足&&，满足一个||
return bool1 && bool2;

深度

1.最大深度

//1.参数
TreeNode root
//2.递归函数返回条件
if(root==null) return 0;
//3.递归左右子树
int leftHeight=digui(root.left);
int rightHeight=digui(root.right);
//4.返回
return Math.max(leftHeight,rightHeight)+1;

2.最小深度

//1.参数
TreeNode root
//2.递归函数返回条件
if(root==null) return 0;
//3.递归左右子树
int leftHeight=digui(root.left);
int rightHeight=digui(root.right);
//4.返回
if(root.left==null) return rightHeight+1;
if(root.right==null) return leftHeight+1;
return Math.min(leftHeight,rightHeight)+1;

路径

递归中隐藏回溯

结果和

//1.参数
TreeNode root
//2.递归函数返回条件
if(root==null) return 0;
//3.结果
int count1 = countNodes(root.left);
int count2 = countNodes(root.right);
//4.返回
return count1+count2+1;

二叉搜索树

利用二叉树特性：root.left.val<root.val<root.right.val

1.递归中序

//1.保存前一个节点
private TreeNode pre;
//2.递归函数返回条件
if(root==null)return;
//3.向左递归
digui(root.left)
//4.操作
//5.保存前一个节点
pre = root
//6.向右递归
digui(root.right)

2.最近公共祖先

//元素不重复所以结果唯一
if(root==null || root==p || root==q) return root;
//自底向上遍历寻找
if(root.val>Math.max(p.val,q.val)){//pq都在左子树,直接去左子树找,找到一个就返回
	return lowestCommonAncestor(root.left,p,q);
}
if(root.val<Math.min(p.val,q.val)){//pq都在右子树,直接去右子树找,找到一个就返回
	return lowestCommonAncestor(root.right,p,q);
}
//pq分布于两颗树
return root;

3.修改与构造

1.增加节点

2.删除节点

充分考虑各种情况

1.没找到删除的节点,遍历到空节点直接返回
2.找到删除的节点,左右孩子都为空(叶子节点),直接删除节点,返回NULL为根节点
3.找到删除的节点,删除节点的左孩子为空,右孩子不为空,删除节点,右孩子补位,返回右孩子为根节点
4.找到删除的节点,删除节点的右孩子为空,左孩子不为空,删除节点,左孩子补位,返回左孩子为根节点
5.找到删除的节点,左右孩子节点都不为空,则将删除节点的左子树头结点放到删除节点的右子树的最左面节点的左孩子上,返回删除节点右孩子为新的根节点