《代码随想录》--二叉树（一）

发布时间：2023年12月18日

《代码随想录》--二叉树第一部分

1、二叉树的递归遍历
2、二叉树的迭代遍历
3、统一风格的迭代遍历代码
4、二叉树的层序遍历
226.翻转二叉树

1、二叉树的递归遍历

前序遍历

中序遍历

后序遍历

代码

前序遍历

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        preOrder(root,list);
        return list;
    }
    public void preOrder(TreeNode root,List<Integer> list){
        if(root == null) return;
        list.add(root.val);
        preOrder(root.left,list);
        preOrder(root.right,list);
    }
}

中序遍历

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        inOrder(root,list);
        return list;
    }
    public void inOrder(TreeNode root,List<Integer> list){
        if(root == null) return;
        inOrder(root.left,list);
        list.add(root.val);
        inOrder(root.right,list);
    }
}

后序遍历

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        postOrder(root,list);
        return list;
    }
    public void postOrder(TreeNode root,List<Integer> list){
        if(root == null) return;
        postOrder(root.left,list);
        postOrder(root.right,list);
        list.add(root.val);
    }
}

2、二叉树的迭代遍历

前序遍历

中序遍历

后序遍历

代码

前序遍历

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if(root == null) return result;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if(node.right != null) stack.push(node.right);
            if(node.left != null) stack.push(node.left);
        }
        return result;
    }
}

中序遍历

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()){
            if(cur != null){
                stack.push(cur);
                cur = cur.left;
            }else{
                TreeNode node = stack.pop();
                list.add(node.val);
                cur = node.right;
            }
        }
        return list;
    }
}

后序遍历

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        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;
    }
}

分析

非递归的遍历都需要借助栈来编写代码
前序遍历：
- 前序遍历是中左右的顺序
- 先把中间节点放入栈中
- 再放入右孩子(为什么？因为栈先入后出)
- 再放入左孩子
中序遍历：
- 中序遍历的顺序是左中右，但是我们的处理顺序和访问顺序不一致，所以借助指针
- 定义一个cur指针帮助我们遍历，栈用来处理节点上的元素
后序遍历：
- 后序遍历的顺序是左右中，可以根据前序遍历改变得到
- 将遍历顺序改为中左右，最后得到的结果是中右左
- 反转数组得到正确结果

3、统一风格的迭代遍历代码

前面的迭代遍历代码风格不统一，不像递归代码一样修改代码的位置就能写出三种遍历方式
这里借助空节点标记法

代码

前序

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root != null) stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.peek();
            if(node != null){
                node = stack.pop();
                if(node.right != null) stack.push(node.right);
                if(node.left != null) stack.push(node.left);
                stack.push(node);
                stack.push(null);
            }else{
                stack.pop();
                node = stack.pop();
                list.add(node.val);
            }
        }
        return list;
    }
}

中序

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root != null) stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.peek();
            if(node != null){
                node = stack.pop(); //将该节点弹出
                if(node.right != null) stack.push(node.right); //添加左节点
                stack.push(node); //添加中节点
                stack.push(null); //中间节点访问过，但是还没有处理，加入空节点标记
                if(node.left != null) stack.push(node.left); //添加右节点
            }else{
                stack.pop(); //弹出空节点
                node = stack.pop(); //取出栈中元素
                list.add(node.val);
            }
        }
        return list;
    }
}

后序

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root != null) stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.peek();
            if(node != null){
                node = stack.pop();
                stack.push(node);
                stack.push(null);
                if(node.right != null) stack.push(node.right);
                if(node.left != null) stack.push(node.left);
            }else{
                stack.pop();
                node = stack.pop();
                list.add(node.val);
            }
        }
        return list;
    }
}

分析

可以看到使用空节点标记法，只需要修改两行代码就能写出不同的遍历代码

4、二叉树的层序遍历

学会二叉树的层序遍历，可以一口气打完以下十题：

代码 102题

迭代

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if(root == null) return list;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> tempList = new ArrayList<>();
            int len = queue.size();
            while(len > 0){
                TreeNode node = queue.poll();
                tempList.add(node.val);
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
                len--;
            }
            list.add(tempList);
        }
        return list;
    }
}

递归

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        level(root,list,0);
        return list;
    }
    public void level(TreeNode node,List<List<Integer>> list,int depth){
        if(node == null) return;
        depth++;
        if(list.size() < depth){
            List<Integer> tempList = new ArrayList<>();
            list.add(tempList);
        }
        list.get(depth-1).add(node.val);
        level(node.left,list,depth);
        level(node.right,list,depth);
    }
}

分析

迭代法借助了数据结构队列，先入先出。

226.翻转二叉树

leetcode链接
在这里插入图片描述

代码

前序遍历

class Solution {
    public TreeNode invertTree(TreeNode root) {
        preOrderReverse(root);
        return root;
    }
    public void preOrderReverse(TreeNode node){
        if(node == null) return;
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
        preOrderReverse(node.left);
        preOrderReverse(node.right);
    }
}

后序遍历

class Solution {
    public TreeNode invertTree(TreeNode root) {
        preOrderReverse(root);
        return root;
    }
    public void preOrderReverse(TreeNode node){
        if(node == null) return;
        preOrderReverse(node.left);
        preOrderReverse(node.right);
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
    }
}

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null) return root;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(queue.size()>0){
            int size = queue.size();
            for(int i = 0;i < size;i++){
                TreeNode node = queue.poll();
                TreeNode temp = node.left;
                node.left = node.right;
                node.right = temp;
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
        }
        return root;
    }
}

统一法

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null) return root;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.peek();
            if(node != null){
                stack.pop();
                if(node.right != null) stack.push(node.right);
                if(node.left != null) stack.push(node.left);
                stack.push(node);
                stack.push(null);
            }else{
                stack.pop();
                node = stack.pop();
                TreeNode temp = node.left;
                node.left = node.right;
                node.right = temp;
            }
        }
        return root;
    }
}

分析

第一种递归的方式，只能写前序和后序，中序代码会导致有些节点反转了两次
第二种BFS，也就是层序遍历
第三种，统一的写法满足前中后序三种遍历方式

文章来源:https://blog.csdn.net/zzz479/article/details/135003924
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！