算法--二叉树遍历

2023-09-11

字数统计: 1.3k字 | 阅读时长≈ 6分

二叉树遍历：

深度遍历：
- 前序遍历：值左右
- 中序遍历：左值右
- 后续遍历：左右值
广度遍历：层序遍历

前序遍历：（递归）

public List<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> res=new ArrayList<>();
        if (root==null){
            return res;
        }
        res.add(root.val);//值
        preorderTraversal(root.left);//左
        preorderTraversal(root.right);//右
        return res;
}

（非递归）

public List<Integer> preTraversal(TreeNode root) {
    ArrayList<Integer> res = new ArrayList<>();
    TreeNode t=root;
    LinkedList<TreeNode> stack = new LinkedList<>();//存放回来路径
    TreeNode poll=null;//记录最近一次弹栈的结点
    while (t!=null||!stack.isEmpty()){
        if (t!=null) {
            stack.push(t);
            res.add(t.val);/*处理左子树前打印*/
            //处理左子树
            t = t.left;
        }else {//左子树处理完，要么弹栈处理结点，要么处理右子树
            TreeNode peek = stack.peek();
            if (peek.right==null){//栈顶元素的右子树为空，不用处理右子树，可以弹栈处理结点
                poll = stack.poll();
            } else if (peek.right==poll) {//最近弹栈的元素==栈顶元素右子树，说明右子树处理完成，可以弹栈
                poll=stack.poll();
            }else {
                //处理右子树
                t=peek.right;
            }
        }
    }
    return res;
}

中序遍历：（递归）

public List<Integer> inorderTraversal(TreeNode root) {
    ArrayList<Integer> res = new ArrayList<>();
    if (root==null){
        return res;
    }
    inorderTraversal(root.left);//左
    res.add(root.val);//右
    inorderTraversal(root.right);//值
    return res;
}

（非递归）

public List<Integer> inTraversal(TreeNode root) {
    ArrayList<Integer> res = new ArrayList<>();
    TreeNode t=root;
    LinkedList<TreeNode> stack = new LinkedList<>();//存放回来路径
    TreeNode poll=null;//记录最近一次弹栈的结点
    while (t!=null||!stack.isEmpty()){
        if (t!=null) {
            stack.push(t);
            //处理左子树
            t = t.left;
        }else {//左子树处理完，要么弹栈处理结点，要么处理右子树
            TreeNode peek = stack.peek();
            if (peek.right==null){//栈顶元素的右子树为空，不用处理右子树，可以弹栈处理结点
                poll = stack.poll();
                res.add(poll.val);  /*打印结点*/
            } else if (peek.right==poll) {//最近弹栈的元素==栈顶元素右子树，说明右子树处理完成，可以弹栈
                poll=stack.poll();
            }else {
                res.add(peek.val); /*处理右子树前打印结点*/
                //处理右子树
                t=peek.right;
            }
        }
    }
    return res;
}

后续遍历：（递归）

public List<Integer> postorderTraversal(TreeNode root) {
    ArrayList<Integer> res =new ArrayList<>();
    if (root==null){
        return res;
    }
    postorderTraversal(root.left);//左
    postorderTraversal(root.right);//右
    res.add(root.val);//值
    return res;
}

(非递归)

public List<Integer> postTraversal(TreeNode root) {
    ArrayList<Integer> res = new ArrayList<>();
    TreeNode t=root;
    LinkedList<TreeNode> stack = new LinkedList<>();//存放回来路径
    TreeNode poll=null;//记录最近一次弹栈的结点
    while (t!=null||!stack.isEmpty()){
        if (t!=null) {
            stack.push(t);
            //处理左子树
            t = t.left;
        }else {//左子树处理完，要么弹栈处理结点，要么处理右子树
            TreeNode peek = stack.peek();
            if (peek.right==null){//栈顶元素的右子树为空，不用处理右子树，可以弹栈处理结点
                poll = stack.poll();
                res.add(poll.val);  /*打印结点*/
            } else if (peek.right==poll) {//最近弹栈的元素==栈顶元素右子树，说明右子树处理完成，可以弹栈
                poll=stack.poll();
                res.add(poll.val); /*处理完右子树后打印结点*/
            }else {
                //处理右子树
                t=peek.right;
            }
        }
    }
    return res;
}

广度遍历：

public static List<List<Integer>> levelOrder(TreeNode root) {
    ArrayList<List<Integer>> result = new ArrayList<>();
    if (root==null){
        return result;
    }
    LinkedList<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()){
        ArrayList<Integer> l = new ArrayList<>();
        //size为每层节点数，需在for循环外（每次for循环都会改变size的值，需求整个for结束后size的值，整个for会把父节点都出队，孩子都入队）
        int size=queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            l.add(node.val);
            if (node.left!=null){
                queue.add(node.left);
            }
            if (node.right!=null){
                queue.add(node.right);
            }
        }
        result.add(l);
    }
    return result;
}

二叉树最大深度：

/**
 * 后续遍历思路（递归效率较高）（可用非递归完成）（另一种思路层序遍历：有几层就是树的最大深度）
 * @param root
 * @return
 */
public int maxDepth(TreeNode root) {
    if (root==null){
        return 0;
    }
    int l = maxDepth(root.left);
    int r = maxDepth(root.right);
    return Math.max(l,r)+1;
}

二叉树最小深度：

/**
 * 层序遍历思路（效率较高）:找到第一个叶子结点的层数就是最小深度
 * @param root
 * @return
 */
public int minDepth1(TreeNode root) {
    if (root==null){
        return 0;
    }
    LinkedList<TreeNode> queue=new LinkedList();
    queue.offer(root);
    int depth=0;
    while (!queue.isEmpty()){
        int c1=queue.size();//每一层结点数
        depth++;
        for (int i = 0; i < c1; i++) {
            TreeNode poll = queue.poll();
            if (poll.left==null&&poll.right==null){
                return depth;
            }
            if (poll.left!=null){
                queue.offer(poll.left);
            }
            if (poll.right!=null){
                queue.offer(poll.right);
            }
        }
    }
    return depth;
}

/**
 * 后续遍历思路（可用非递归）
 * @param root
 * @return
 */
public int minDepth(TreeNode root) {

    //若结点为空，深度为0
    if (root==null){
        return 0;
    }

    //若结点只有一边子树，返回该边子树深度+该节点深度1
    if (root.left==null){
        return minDepth(root.right)+1;
    }
    if (root.right==null){
        return minDepth(root.left)+1;
    }

    //若结点有两边子树，返回该节点的左子树和右子树的深度较小的+该节点深度1
    int l = minDepth(root.left);
    int r = minDepth(root.right);
    return Math.min(l,r)+1;
}

本文作者： zzr
本文链接： http://zzruei.github.io/2023/09f0b58408.html
版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！