二叉树的定义

跟链表的定义方式比较像

class BinaryNode<AnyType> {
    AnyType element;       // The data in the node
    BinaryNode<AnyType> left;     // Left child
    BinaryNode<AnyType> right;    // right child
    public BinaryNOode(AnyType element) {
        this(element,null,null);
    }
    public BinaryNOode(AnyType element, BinaryNode<AnyType> left,BinaryNode<AnyType> right) {
        this.element = element;
        this.right = right;
        this.left = left;
    }
}

// Definition for a binary tree node.
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;
     }
}

二叉树的遍历

深度优先遍历

前、中、后序递归遍历(递归法)

递归三部曲：

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

2、确定终止条件

3、确定单层递归的逻辑

144.二叉树的前序遍历(递归)

// 前序遍历·递归
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        // 创建返回值
        List<Integer> result = new ArrayList<>();
        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);
    }
}

94.二叉树的中序遍历(递归)

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inOrder(root,result);
        return result;
    }
    // 确定递归的参数和返回值
    public void inOrder (TreeNode root, List<Integer> result) {
        // 确定终止条件
        if (root == null) {
            return;
        }
        // 确定单层递归的逻辑
        inOrder(root.left,result);
        result.add(root.val);
        inOrder(root.right,result);
    }
}

145.二叉树的后序遍历(递归)

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        postOrder(root,result);
        return result;
    }
    public void postOrder(TreeNode root, List<Integer> result){
        // 确定终止条件
        if (root == null) {
            return;
        }
        postOrder(root.left , result);
        postOrder(root.right , result);
        result.add(root.val);
    }
}

前、中、后序迭代遍历(迭代法)

迭代法的操作主要分为两步：

1、访问节点

2、处理节点

144.二叉树的前序遍历(迭代)

前序遍历时中左右，所以我们希望节点从栈中弹出来的时候也是中左右。

上图是对一个二叉树的代码模拟，画一遍更有感觉，其实循环中每次都是父节点被弹出添加，然后临走前将右节点和左节点添加进去，后面就按照左右的顺序出战

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        // 创建接收集合
        List<Integer> result = new ArrayList<>();
        // 防止空树
        if (root == null) {
            return result;
        }
        // 创建栈
        Deque<TreeNode> stack = new LinkedList<>();
        // 首先先将根节点压栈
        stack.push(root);
        // 迭代操作
        while (!stack.isEmpty()) {
            // 获取栈顶元素
            TreeNode node = stack.peek();
            // 将栈顶元素弹出，并添加到集合中
            result.add(stack.pop().val);
            // 获取节点的右子树，因为后弹出的要先压入
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return result;
    }
}

145.二叉树的后序遍历(迭代)

前序遍历的代码完成之后，如果将循环中先访问右节点再访问左节点，变换成先访问左节点再访问右节点，这样对二叉树的遍历顺序就成了中->右->左了，这样刚好是后序遍历的倒序，那么将最后获取到的数组反转就是后序遍历了

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        // 创建接收集合
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        // 创建栈
        Deque<TreeNode> stack = new LinkedList<>();
        // 首先先将根节点压栈
        stack.push(root);
        // 迭代操作
        while (!stack.isEmpty()) {
            // 获取栈顶元素，一会要拿着这个元素判断它的左右子树
            TreeNode node = stack.peek();
            // 将栈顶元素弹出，并添加到集合中
            result.add(stack.pop().val);
            // 压入节点的左子树，因为后弹出的要先压入
            if (node.left != null) {
                stack.push(node.left);
            }
            // 再压入节点的右子树
            if (node.right != null) {
                stack.push(node.right);
            }           
        }
        // 至此 集合中保存的其实是 中->右->左的遍历顺序
        // 将遍历到的结果反转过来就是 左->右->中的遍历顺序了
        Collections.reverse(result);
        return result;
    }
}

94.二叉树的中序遍历(迭代)

在迭代代码的时候会分两步进行操作：

1、对节点的访问：遍历节点

2、对节点的处理：将节点中的val添加到数组中

前序遍历的顺序是中左右，我们是从根节点(中间节点)入手的，访问到了根节点之后就对根节点进行了处理

但是中序遍历的顺序是左中右，先访问的是根节点(中间节点)，访问到了中间节点之后不能对中间节点进行处理，而是要继续向左子树访问，一层一层下去，知道最左边的元素，再开始对节点进行处理

所以前面只能访问，不能处理

那就只能借助指针进行访问，访问到目的元素之后再进行处理

访问：从根节点开始一路向左进行访问，只要左子树有节点，那就进行压栈，其实压的这些都是“中”

处理：当访问的节点的左侧再没有节点的时候，将栈中的栈顶弹出，再去访问弹出节点的右子树

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        // 创建接收数组
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        // 创建栈
        Deque<TreeNode> stack = new ArrayDeque<>();
        // 创建指针
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) { // 如果节点不是空，那就将节点添加到栈中，继续寻找左孩子
                stack.push(cur);
                cur = cur.left;
            } else {           // 如果节点为空了，那就说明没有左孩子了，压进去的节点可以弹出了，然后去看弹出节点的右孩子
                TreeNode node = stack.pop();
                result.add(node.val);
                cur = node.right;
            }
        }
        return result;
    }
}

前、中、后序统一迭代

统一迭代法的书写风格，待定学习

广度优先遍历

二叉树的层序遍历

120.二叉树的层序遍历 力扣

层序遍历真的是思路简单，代码舒适呀。顾名思义，层序遍历就是对二叉树的每一层从左到右进行遍历

层序遍历需要借助队列来实现遍历，队列是先进先出，适合层序遍历的逻辑

有几个需要注意的点：

1、先将根节点入队，这样在进入循环，根据根节点开始进入循环

2、每次循环第一步，就是要判断这一层有几个节点，也就是队列的长度，获取当下的固定值，是一会要出队的个数

3、每次出一个节点，就把它的左孩子节点和右孩子节点添加进去

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        // 创建队列
        Deque<TreeNode> queue = new ArrayDeque<>();
        // 先将根节点添加进队列
        queue.offer(root);
        while (!queue.isEmpty()) {
            // 获取次数队列的长度，这代表着这一层有几个节点，是一会出队的界限
            int size = queue.size();
            List<Integer> temp = new ArrayList<>();
            while (size-- > 0) {
                TreeNode node = queue.poll();
                temp.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            result.add(temp);
        }
        return  result;
    }
}

代码随想录刷题|二叉树的理论基础、二叉树的遍历 LeetCode 144、145、94、120（下）

二叉树的定义

二叉树的遍历

深度优先遍历

前、中、后序递归遍历(递归法)

前、中、后序迭代遍历(迭代法)

前、中、后序统一迭代

广度优先遍历

二叉树的层序遍历

热门文章

最新文章

相关电子书

代码随想录刷题|二叉树的理论基础、 二叉树的遍历 LeetCode 144、145、94、120（下）

二叉树的定义

二叉树的遍历

深度优先遍历

前、中、后序递归遍历(递归法)

前、中、后序迭代遍历(迭代法)

前、中、后序统一迭代

广度优先遍历

二叉树的层序遍历

热门文章

最新文章

相关电子书

代码随想录刷题|二叉树的理论基础、二叉树的遍历 LeetCode 144、145、94、120（下）