代码随想录算法训练营day13

基础知识

二叉树基础知识

二叉树多考察完全二叉树、满二叉树，可以分为链式存储和数组存储，父子兄弟访问方式也有所不同，遍历也分为了前中后序遍历和层次遍历

Java定义

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

递归遍历

这个简单就不赘述了

迭代遍历

考研期间跟着王道走过一遍迭代遍历，建议画个简单的数模拟一下，自然写出代码，画图模拟

/**
* 前序 深度相关
*/
public List<Integer> preOrder(TreeNode root) {
    TreeNode p = root;
    ArrayDeque<TreeNode> stack = new ArrayDeque<>();
    // 存放结果 visit操作
    List<Integer> result = new ArrayList<>();
    // p不空，或者栈不空，表示要进行入栈或出栈操作，两个都空表示结束
    while (p != null || !stack.isEmpty()) {
        if (p != null) {
            // visit p
            result.add(p.val);
            stack.push(p);
            p = p.left;
        } else {
            p = stack.pop();
            p = p.right;
        }
    }
    return result;
}
/**
* 中序 顺序相关
*/
public List<Integer> inOrder(TreeNode root) {
    TreeNode p = root;
    ArrayDeque<TreeNode> stack = new ArrayDeque<>();
    // 存放结果 visit操作
    List<Integer> result = new ArrayList<>();
    // p不空，或者栈不空，表示要进行入栈或出栈操作，两个都空表示结束
    while (p != null || !stack.isEmpty()) {
        if (p != null) {
            stack.push(p);
            p = p.left;
        } else {
            p = stack.pop();
            // visit p
            result.add(p.val);
            p = p.right;
        }
    }
    return result;
}
/**
* 后序遍历 高度相关
*/
public List<Integer> postOrder(TreeNode root) {
    TreeNode p = root;
    // 每个点都可能有一个右孩子，在访问根节点之前要保证访问过它的右孩子
    TreeNode r = null;
    ArrayDeque<TreeNode> stack = new ArrayDeque<>();
    // 存放结果 visit操作
    List<Integer> result = new ArrayList<>();
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                // 走到树的最左边
                p = p.left;
            } else {
                // 读栈顶指针，这里是乐观思路
                p = stack.peek();
                // 若右子树存在且未被访问
                if (p.right != null && p.right != r) {
                    p = p.right;
                } else {
                    p = stack.pop();
                    // visit
                    result.add(p.val);
                    // 更新被访问点
                    r = p;
                    // 重置p指针，从栈中获取
                    p = null;
                }
            }
        }
    return result;
}

总结

递归三要素

确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数，并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。