最近在做课设,但是又想到,春招面试的时候会问各种算法题,还有什么高并发,多线程,数据库那些问题,学不来了...所以这些也不能断,还得天天搞搞。现在开始刷刷二叉树相关的题,先把基础的遍历做好。

二叉树的遍历有四种,分别是前序遍历中序遍历后序遍历层次遍历,下面展示下各种遍历的迭代和递归做法。

前序遍历

前序遍历的“前”表示中间结点在遍历时候的位置,这种遍历方式就是先访问中间结点,然后是左子树和右子树。可以很简单地写出递归的代码:

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    preOrder(root, res);
    return res;
}
private 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> list = new ArrayList<>();
    if (root == null){
        return list;
    }
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()){
        TreeNode node = stack.pop();
        list.add(node.val);
        if (node.right != null){
            stack.push(node.right);
        }
        if (node.left != null){
            stack.push(node.left);
        }
    }
    return list;
}

中序遍历

前、中、后序遍历的递归方式很相似,只是改变一下递归的语句。按照中序遍历的语义,它是先访问左子树,然后访问中间结点,最后访问右子树,那么递归的方式也是一样的。

List<Integer> ans = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
    dfs(root);
    return ans;
}
public void dfs(TreeNode root){
    if(root == null){
        return ;
    }
    dfs(root.left);
    ans.add(root.val);
    dfs(root.right);
}

迭代写法又与前序的不一致,它的大意是一直往左边找,直到尽头,就把中间元素放入结果中,然后右转,再继续往左找。。。

public List<Integer> inorderTraversal(TreeNode root) {
    ArrayList<Integer> list = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        if (cur != null){
            stack.push(cur);
            // 一路向左
            cur = cur.left;
        }else{
            cur = stack.pop();
            // 处理元素
            list.add(cur.val);
            cur = cur.right;
        }
    }
    return list;
}

后序遍历

List<Integer> ans = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
    dfs(root);
    return ans;
}
public void dfs(TreeNode root){
    if(root == null){
        return ;
    }
    dfs(root.left);
    dfs(root.right);
    ans.add(root.val);
}

后序遍历的迭代方式和前序很像,因为后序是左右中,而前序是中左右,可以把前序的顺序改一下,变成中右左,再逆序,即为后序的遍历方式。

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            list.add(node.val);
            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
        }
        Collections.reverse(list);
        return list;
    }

通用的迭代遍历方式

刚刚可以看到,前、中、后序的迭代遍历方式各有点不同,下面有一套通用的方式处理迭代,可能有、难理解。
仍然是使用,但是它遇到要处理的元素时不是马上放入结果,而是继续把它放入栈,只是在它后面加一个占位符(这里为空),当下次遍历到空时,就知道它是要处理的元素。
我认为,本质上是使用栈改变它们的顺序,然后依次取值即为想要的遍历结果。 ?

下面上代码 :

/**
  *  这里展示的是中序遍历的通用模版
*/
public List<Integer> commonTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    // 因为ArrayDeque不能放null,所以改用Stack
    Stack<TreeNode> stack = new Stack<>();
    if (root != null) {
        stack.push(root);
    }
    while (!stack.isEmpty()){
        TreeNode node = stack.pop();
        if (node != null){
            // 这里是右、中、左,那根据栈先进后出的特性
            // 其实它真实的遍历顺序是左中右,即为中序遍历
            /*---顺序变更的地方---*/
            if (node.right != null) {
                stack.push(node.right);
            }
            // 访问了,但是还没处理
            stack.push(node);
            stack.push(null);
            if (node.left != null) {
                stack.push(node.left);
            }
            /*---顺序变更的地方---*/
        }else{
            node = stack.pop();
            list.add(node.val);
        }
    }
    return list;
}

要变化的是注释中间的地方。

可以看到,要处理的node结点后面都会放一个null。在纸上写写,会发现最后每个元素后面都会垫一个null,然后再处理....这确实是通用的模块,好吧。

层次遍历

这个遍历方式使用了队列这种数据结构,每次都遍历“一层”的元素,然后依次把下一层的元素放入,直到队列为空。

public List<List<Integer>> levelOrder2(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    Deque<TreeNode> queue = new ArrayDeque<>();
    if (root != null) {
        queue.offer(root);
    }
    while (!queue.isEmpty()) {
        ArrayList<Integer> list = new ArrayList<>();
        // 遍历一层的元素
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            list.add(node.val);
            // 按照顺序再放入,即下一层的左、右
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        res.add(list);
    }
    return res;
}

还有一种递归的方式,使用了层数这个变量,非常巧妙,ummmmmmmmmm我一时也说不上来。

List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
    dfs(root, 0);
    return res;
}

private void dfs(TreeNode root, int deep) {
    if (root == null) {
        return;
    }
    // 加位置,不然没得放
    if (deep >= res.size()) {
        res.add(new ArrayList<>());
    }
    res.get(deep).add(root.val);
    dfs(root.left, deep + 1);
    dfs(root.right, deep + 1);
}

小结

按照某些dl的说法,这几种遍历方式都会了,二叉树的问题也就解决了大半【x】

希望如此,继续刷刷刷了。