首页算法

# 递归遍历

确定下来递归算法的三个要素。每次写递归，都按照这三要素来写，可以保证写出正确的递归算法！

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

# 前序遍历

以下以前序遍历为例：

  1. 确定递归函数的参数和返回值：因为要打印出前序遍历节点的数值，所以参数里需要传入 vector 在放节点的数值，除了这一点就不需要在处理什么数据了也不需要有返回值，所以递归函数返回类型就是 void，代码如下：
void preorder(TreeNode root, List<Integer> result)
  1. 确定终止条件：在递归的过程中，如何算是递归结束了呢，当然是当前遍历的节点是空了，那么本层递归就要要结束了，所以如果当前遍历的这个节点是空，就直接 return，代码如下：
if (root == null) {
    return;
}
  1. 确定单层递归的逻辑：前序遍历是中左右的循序，所以在单层递归的逻辑，是要先取中节点的数值，代码如下：
result.add(root.val);    // 中
preorder(root.left, result);  // 左
preorder(root.right, result); // 右

单层递归的逻辑就是按照中左右的顺序来处理的，这样二叉树的前序遍历，基本就写完了，再看一下完整代码：

前序遍历：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        preorder(root, result);
        return result;
    }
    public void preorder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        result.add(root.val);
        preorder(root.left, result);
        preorder(root.right, result);
    }
}
# 中序遍历


class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorder(root, res);
        return res;
    }
    void inorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        inorder(root.left, list);
        list.add(root.val);             // 注意这一句
        inorder(root.right, list);
    }
}
# 后序遍历


145. 二叉树的后序遍历 - 力扣（LeetCode）


class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postorder(root, res);
        return res;
    }
    void postorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        postorder(root.left, list);
        postorder(root.right, list);
        list.add(root.val);             // 注意这一句
    }
}
# 迭代遍历


# 前序遍历


我们先看一下前序遍历。


前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。


为什么要先加入 右孩子，再加入左孩子呢？ 因为这样出栈的时候才是中左右的顺序。


// 前序遍历顺序：中 - 左 - 右，入栈顺序：中 - 右 - 左
class Solution {
    // 迭代，栈
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList();
        Deque<TreeNode> right = new LinkedList();
        while(root != null || !right.isEmpty()){
            while(root!=null){
                res.add(root.val);
                // 把当前节点放入栈
                right.offerFirst(root);
                root = root.left;
            }
            // 获取每次节点的右孩子并删除该节点
            root = right.poll();
            root = root.right;
        }
        return res;
    }
}
# 中序遍历（迭代法）


中序遍历，可以写出如下代码：


// 中序遍历顺序：左 - 中 - 右 入栈顺序： 左 - 右
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList();
        Deque<TreeNode> stack = new LinkedList();
        while(!stack.isEmpty() || root!=null){// 最左边的结束了 root = null，返回上一父节点 
            while(root != null){
                stack.offerFirst(root);
                root = root.left;
            }
            // 找到最左边的节点
            root = stack.pollFirst();
            res.add(root.val);
            // 继续遍历右孩子
            root = root.right;
        }
        return res;
    }
}
# 后序遍历 - 1


再来看后序遍历，先序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转 result 数组，输出的结果顺序就是左右中了，如下图：


img


所以后序遍历只需要前序遍历的代码稍作修改就可以了，代码如下：


// 后序遍历顺序 左 - 右 - 中 入栈顺序：中 - 左 - 右 出栈顺序：中 - 右 - 左， 最后翻转结果
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList();
        Deque<TreeNode> stack = new LinkedList();
        while(root != null || !stack.isEmpty()){
            while(root!=null){
                res.add(root.val);
                // 把当前节点放入栈
                right.offerFirst(root);
                root = root.right;
            }
            // 获取每次节点的右孩子并删除该节点
            root = right.poll();
            root = root.left;
        }
        Collections.reverse(result);
        return result;
    }
}
# 后序遍历 - 2


img


与中序的不同之处在于：


    

  • 中序遍历中，从栈中弹出的节点，其左子树是访问完了，可以直接访问该节点，然后接下来访问右子树。
    • 

  • 后序遍历中，从栈中弹出的节点，我们只能确定其左子树肯定访问完了，但是无法确定右子树是否访问过。
    • 



因此，我们在后序遍历中，引入了一个  prev  来记录历史访问记录。


    

  • 当访问完一棵子树的时候，我们用  prev  指向该节点。
    • 

  • 这样，在回溯到父节点的时候，我们可以依据  prev  是指向左子节点，还是右子节点，来判断父节点的访问情况。
    • 



class Solution {
    // 左右中
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList();
        if(root == null){
            return res;
        }
        Deque<TreeNode> stack = new LinkedList();
        TreeNode prev = null;// 记录上一节点，因为后面要一个一个返回根，如果根的右节点等于 prev，则返回根
        while(root != null || !stack.isEmpty()){
            // 找到最左边
            while(root != null){
                stack.offerFirst(root);
                root = root.left;
            }
            // 弹出 m 左边
            root = stack.pollFirst();
            //root.right == null 没有右孩子
            // 例如：节点 7 遍历完返回节点 4, 此时 prev = 7
            //	- 若没有这个判断 root.right == prev, 则进入 else 再次将 7 压入栈
            if(root.right == null || root.right == prev){
                res.add(root.val);
                // 不弄 prev 会死循环
                prev = root;
                // 将该节点引用指向 null, 从栈顶弹出新的元素
                root = null;// 说明这个节点走过
            } else {
                stack.offerFirst(root);
                root = root.right;
            }
            
        }
        return res;
    }
}
# morris 遍历


# 中序遍历


# 具体步骤


如下图所示二叉树，对于节点 1 首先保存其左孩子节点 2, 并获取其左孩子节点 2 的最右孩子 5, 然后将节点 1 及其右子树挂到节点 5 的右子树


img


然后将当前节点更新为节点 2, 并且重复上述步骤：保存节点 4 并将节点 2 及其右子树挂到节点 4 的最右孩子的右子树上


img


将当前节点更新为节点 4, 此时节点 4 的左孩子为空，则将节点 4 放入结果集，并更新当前节点为节点 4 的右孩子节点 2。


此时当前节点为节点 2，保存节点 2 的左孩子节点 4，并获取节点 4 的最右边节点。


    

  • 但是，节点 4 的右孩子等于当前节点 2，即：left.right==rootleft.right == root
    • 



对节点 4 进行断链操作，即将节点 4 的右孩子置空，还原到原始的状态，并且更新当前节点为节点 2 的右孩子节点 5。如下图所示


    

  • left.right=nullleft.right = null
    • 



img




发现节点 5 的左孩子为 null，继续更新当前节点为节点 5 的右孩子节点 1。同样的进行断链操作。


img


...




# 细节步骤图片


img




img


# 具体代码


//morris 不破坏原有结构
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        TreeNode cur = null;
        while(root != null){
            if(root.left != null){
                //cur 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止
                cur = root.left;
                while(cur.right != null && cur.right != root){
                    cur = cur.right;
                }
				// 让 cur 的右指针指向 root，继续遍历左子树
                if(cur.right == null){
                    cur.right = root;
                    root = root.left;
                }else{// 说明 root 的左子树访问完了。断开原先设置的链接
                    res.add(root.val);
                    cur.right = null;
                    root = root.right;
                }
            }else{// 如果没有左孩子，直接访问右孩子
                res.add(root.val);
                root = root.right;
            }
        }
        return res;
    }
}
# 前序遍历


前序遍历，更中序的思路是一样的，只不过加入结果集的位置不一样。


//morris  前序遍历，更中序的思路是一样的
class Solution {
    // 根左右
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList();
        TreeNode cur = null;
        while(root != null){
            if(root.left != null){
                cur = root.left;
                while(cur.right != null && cur.right != root){
                    cur = cur.right;
                }
                if(cur.right == null){
                    res.add(root.val);
                    cur.right = root;
                    root = root.left;
                }else{
                    cur.right = null;// 断开之前建立的连接
                    root = root.right;
                }
            }else{
                res.add(root.val);
                root = root.right;
            }
        }
        return res;
    }
}
# 后序遍历


左右根：就是上面前序遍历（ morris  根左右）的镜像根右左，再反转


class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList();
        TreeNode cur = null;
        while(root != null){
            if(root.right != null){
                cur = root.right;
                while(cur.left != null && cur.left != root){
                    cur = cur.left;
                }
                if(cur.left == null){
           		 	res.add(root.val);
                    cur.left = root;
                    root = root.right;
                }else{
                    cur.right = null;// 断开之前建立的连接
                    root = root.left;
                }
            }else{
                res.add(root.val);
                root = root.left;
            }
        }
        Collections.reverse(res);
        return res;
    }
}
# 二叉树的层次遍历


层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。


需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而是用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。


而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。


class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList();
        if(root == null){
            return res;
        }
        Deque<TreeNode> queue = new LinkedList();
        queue.offerLast(root);
        while(!queue.isEmpty()){
            // 获取每次的节点
            List<Integer> list = new ArrayList();
            // 每次大迭代，队列的长度就是整个个数
            int size = queue.size();
            // 遍历的加入 list
            while(size-- > 0){
                root =  queue.removeFirst();
                list.add(root.val);
                // 左节点不为空，加入队列，个数 + 1
                if(root.left != null){
                    queue.offerLast(root.left);
                }
                // 右节点不为空，加入队列，个数 + 1
                if(root.right != null){
                    queue.offerLast(root.right);
                }
            }
            res.add(list);
        }
        return res;
    }
}