欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

常见算法总结 - 二叉树篇

程序员文章站 2022-07-01 12:59:24
本文总结了常见高频的关于二叉树的算法考察。 1.计算一个给定二叉树的叶子节点数目。 可以采用递归的方式进行累加 2.计算二叉树的深度。 跟上题一样采用递归的方式,但需返回左右子树中较深的深度。 3.如何打印二叉树每层的节点。 借助一个队列,先把根节点入队,每打印一个节点的值时,也就是打印队列头的节点 ......

本文总结了常见高频的关于二叉树的算法考察。

1.计算一个给定二叉树的叶子节点数目。

可以采用递归的方式进行累加

public static int calculatetreenodenumber(treenode treenode) {

        if (treenode == null) {
            return 0;
        }

        return calculatetreenodenumber(treenode.left) + calculatetreenodenumber(treenode.right) + 1;

}

2.计算二叉树的深度。

跟上题一样采用递归的方式,但需返回左右子树中较深的深度。

public static int gettreedepth(treenode tree) {

        if (tree == null) {
            return 0;
        }

        int left = gettreedepth(tree.left);
        int right = gettreedepth(tree.right);

        return left >= right ? left + 1 : right + 1;
}

3.如何打印二叉树每层的节点。

借助一个队列,先把根节点入队,每打印一个节点的值时,也就是打印队列头的节点时,都会把它的的左右孩子入队,并且把该节点出队。直到队列为空。

public static void printbylevel(treenode tree) {
        if (tree == null) {
            return;
        }

        linkedlist<treenode> queue = new linkedlist<>();
        queue.add(tree);
        
        while (!queue.isempty()) {
            treenode pop = queue.pop();
            system.out.println(pop.val);
            if (pop.left != null) {
                queue.add(pop.left);
            }
            if (pop.right != null) {
                queue.add(pop.right);
            }
        }

}

4.二叉树的z型遍历。

借助两个队列,一个正序打印,一个逆序打印。

 public static void printbyz(treenode tree) {

        if (tree == null) {
            return;
        }

        list<treenode> orderqueue = new arraylist<>();
        list<treenode> disorderqueue = new arraylist<>();

        orderqueue.add(tree);

        while (!orderqueue.isempty()|| !disorderqueue.isempty()) {
            if (!orderqueue.isempty()) {
              for (int i = 0; i < orderqueue.size(); i++) {
                    treenode leaf = orderqueue.get(i);
                    if (leaf.left != null) {
                        disorderqueue.add(leaf.left);
                    }
                    if (leaf.right != null) {
                        disorderqueue.add(leaf.right);
                    }
                }

                for (treenode node : orderqueue) {
                    system.out.println(node.val);
                }
                orderqueue.clear();
              
            }


            if (!disorderqueue.isempty()) {

                for (int i = 0; i < disorderqueue.size(); i++) {
                    treenode leaf = disorderqueue.get(i);
                    if (leaf.left != null) {
                        orderqueue.add(leaf.left);
                    }
                    if (leaf.right != null) {
                        orderqueue.add(leaf.right);
                    }
                }

                for (int i = disorderqueue.size()-1; i >=0 ; i--) {
                    treenode leaf = disorderqueue.get(i);
                    system.out.println(leaf.val);
                }
                disorderqueue.clear();
            }
        }

    }

5.一个已经构建好的treeset,怎么完成倒排序。

递归更换左右子树即可

public static void reverse(treenode tree) {

        if (tree.left == null && tree.right == null) {
            return;
        }

        treenode tmp = tree.right;

        tree.right = tree.left;
        tree.left = tmp;

        reverse(tree.left);
        reverse(tree.right);

}

6.二叉树的前序遍历。

前序递归

public static void preorderrecursion(treenode tree) {

    if (tree != null) {
        system.out.print(tree.val + "->");
        preorderrecursion(tree.left);
        preorderrecursion(tree.right);
    }

}

前序非递归

public static void preordernonrecursion(treenode tree) {

        stack<treenode> stack = new stack<>();
        treenode node = tree;
        while (node != null || !stack.empty()) {
            if (node != null) {
                system.out.print(node.val + "->");
                stack.push(node);
                node = node.left;
            } else {
                treenode tem = stack.pop();
                node = tem.right;
            }
        }
    }

7.二叉树的中序遍历。

中序递归

public static void middleorderrecursion(treenode tree) {

        if (tree != null) {
            middleorderrecursion(tree.left);
            system.out.print(tree.val + "->");
            middleorderrecursion(tree.right);
        }

}

中序非递归

public static void middleordernonrecursion(treenode tree) {

        stack<treenode> stack = new stack<>();
        treenode node = tree;
        while (node != null || !stack.isempty()) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                treenode tem = stack.pop();
                system.out.print(tem.val + "->");
                node = tem.right;
            }
        }

    }

8.二叉树的后序遍历。

后序递归

public static void postordertraverserecursion(treenode root) {
        if (root != null) {
            postordertraverserecursion(root.left);
            postordertraverserecursion(root.right);
            system.out.print(root.val + "->");
        }
}

后序非递归

public static void postordertraversenonrecursion1(treenode root) {

        linkedlist<treenode> stack = new linkedlist<>();
        linkedlist<treenode> output = new linkedlist<>();
        if (root == null) {
            return;
        }

        stack.add(root);
        while (!stack.isempty()) {

            treenode node = stack.polllast();
            output.addfirst(node);

            if (node.left != null) {
                stack.add(node.left);
            }
            if (node.right != null) {
                stack.add(node.right);
            }
        }

        for (treenode node : output) {
            system.out.print(node.val + "->");
        }

}
笔者个人总结,如有错误之处望不吝指出。

本文转自我的个人博客:《coderv的进阶笔记
欢迎加入java后端架构技术讨论群:1398880
我的公众号:coderv的进阶笔记,记录技术心得
常见算法总结 - 二叉树篇