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

树的基础算法题

程序员文章站 2024-03-22 18:03:40
...

写在前言

递归三部曲:

  1. 找终止条件:什么时候递归到头了?
  2. 思考返回值,每一级递归应该向上返回什么信息?
  3. 单步操作应该怎么写?因为递归就是大量的调用自身的重复操作,因此从宏观上考虑,只用想想单步怎么写就行了,左树和右树应该看成一个整体,即此时树一共三个节点:root,root.left,root.right。

1.二叉树的遍历

1.递归版本

1.前序遍历;先访问根结点,然后再访问左子树,最后访问右子树
2.中序遍历;先访问左子树,中间访问根节点,最后访问右子树。此种方式遍历结果,会使结点有序
3.后序遍历;先访问左子树,再访问右子树,最后访问根节点

	//使用3中方式遍历,获取整个树中的所有值
    public void values(TreeNode root) {
        preErgodic(root);
        midErgodic(root);
        afterErgodic(root);
    }

    /**
     * 前序遍历实现步骤:
     * 1.打印当前节点;
     * 2.找到当前结点的左子树,如果不为空,递归遍历左子树
     * 3.找到当前结点的右子树,如果不为空,递归遍历右子树
     */
    private void preErgodic(TreeNode node) {
        if (node == null) return;//如果当前节点为空,就直接返回
       	System.out.println(node.val);//保存当前节点的值
        if (node.left != null) preErgodic(node.left);//遍历左边
        if (node.right != null) preErgodic(node.right);//遍历右边
    }

    /**
     * 中序遍历实现步骤:
     * 1.找到当前结点的左子树,如果不为空,递归遍历左子树
     * 2.打印当前节点;
     * 3.找到当前结点的右子树,如果不为空,递归遍历右子树
     */
    private void midErgodic(TreeNode node) {
        if(node==null) return;
        if(node.left!=null) midErgodic(node.left);
       	System.out.println(node.val);//保存当前节点的值
        if(node.right!=null) midErgodic(node.right);
    }


    /**
     * 后序遍历实现步骤:
     * 1.找到当前结点的左子树,如果不为空,递归遍历左子树
     * 2.找到当前结点的右子树,如果不为空,递归遍历右子树
     * 3.打印当前节点;
     */
    private void afterErgodic(TreeNode node) {
        if(node == null) return;
        if(node.left!=null) afterErgodic(node.left);
        if(node.right!=null) afterErgodic(node.right);
       	System.out.println(node.val);
    }

2.非递归版本

思想:使用栈,因为递归版本就是系统帮你压栈,则可以想到我们使用非递归版本可以自己手动压栈。

前序遍历:使用一个栈,先把根节点压入进去,然后开始弹栈,然后压入当前节点的右节点,然后再压左节点,因为先进后出嘛,右节点先进去,则后打印

  public void pre(TreeNode root){
        if (root == null) return;
        Stack<TreeNode> stack=new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode curNode = stack.pop();
            System.out.print(curNode.val+" ");//处理节点
            if(curNode.right!=null) stack.push(curNode.right);
            if(curNode.left!=null) stack.push(curNode.left);
        }
    }

中序遍历:也是用一个栈,先把树的左节点全部压入进去,压完左节点就开始弹出一个当前节点,然后处理打印,并让当前节点指向它的右节点,继续循环,如果当前节点为null,就不能压栈,继续出栈

 public void mid(TreeNode root){
        if (root == null) return;
        Stack<TreeNode> stack=new Stack<>();
        while (!stack.isEmpty() || root!=null){
            //如果当前节点不为Null,压栈
            if(root !=null){
                stack.push(root);
                root=root.left;//让当前节点指向它的左子树
            } else {
                root = stack.pop();
                System.out.print(root.val+" ");//处理节点
                root=root.right;//让当前节点指向它的右子树
            }
        }
    }

后序遍历:使用2个栈。stack先压入根节点,然后开始弹出,弹出后将当前节点放到stackNode栈中。如果当前节点有左节点,就压入左节点,如果有右节点,则压入右节点。最后打印stackNode栈就是后序遍历的顺序

 public void after(TreeNode root){
        if (root == null) return;
        Stack<TreeNode> stack=new Stack<>();
        Stack<TreeNode> stackNode=new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode curNode = stack.pop();
            stackNode.push(curNode);
            if(curNode.left!=null) stack.push(curNode.left);
            if(curNode.right!=null) stack.push(curNode.right);
        }
        while (!stackNode.isEmpty())
            System.out.print(stackNode.pop().val+" ");
    }

3.层次遍历

实现步骤:
1.创建队列,存储每一层的结点;
2.使用循环从队列中弹出一个结点:
2.1获取当前结点的key;
2.2如果当前结点的左子结点不为空,则把左子结点放入到队列中
2.3如果当前结点的右子结点不为空,则把右子结点放入到队列中

public Queue<Integer> layerErgodic(){
        Queue<Integer> values=new ArrayDeque<>();
        ArrayDeque<TreeNode> queue=new ArrayDeque<TreeNode>();
        queue.add(root);//让根节点进入队列
        while (!queue.isEmpty()){
            //进入了循环,说明该队列中还有结点,则将该队首出队,保存到values中
            TreeNode node = queue.remove();
            values.add(node.val);
            if(node.left!=null) queue.add(node.left);
            if(node.right!=null) queue.add(node.right);
        }
        return values;
    }

层次遍历进阶版:按层次输入元素:

	public List<List<Integer>> levelOrder(TreeNode root) {
            if(root==null) return new ArrayList<>();
            ArrayDeque<TreeNode> queue=new ArrayDeque<TreeNode>();
            queue.add(root);
            List<List<Integer>> lists=new ArrayList<>();
            while (!queue.isEmpty()){
                List<Integer> layer=new ArrayList<>();
                //进入了循环,说明该队列中还有结点,则将该队首出队,保存到每层的layer中
                int count=queue.size();//用于保存每一层的元素节点个数
                while (count>0){
                    TreeNode node = queue.poll();
                    layer.add(node.val);
                    if(node.left!=null) queue.add(node.left);
                    if(node.right!=null) queue.add(node.right);
                    count--;
                }
                lists.add(layer);
            }
            return lists;
        }

4.树的最大深度

实现步骤:
1.如果根结点为空,则最大深度为0;
2.计算左子树的最大深度;
3.计算右子树的最大深度;
4.当前树的最大深度=左子树的最大深度和右子树的最大深度中的较大者+1

 private int maxDepth(TreeNode node) {
        if(node==null) return 0;//1.如果根结点为空,则最大深度为0;
        int max=0;
        int leftMax=0;
        int rightMax=0;
        if(node.left!=null) leftMax=maxDepth(node.left);
        if(node.right!=null) rightMax=maxDepth(node.right);
        //4.当前树的最大深度=左子树的最大深度和右子树的最大深度中的较大者+1
        max=leftMax>rightMax? leftMax+1:rightMax+1;
        return max;
    }

2.二叉树的最大宽度

树的最大宽度

思想:用两个队列,一个队列存放节点,一个队列存放该节点对应的索引位置,然后每层的最大宽度就是队列最后一个元素(该层的最大节点)索引 - 该层队列的最前面元素索引 + 1

class Solution {
    public int widthOfBinaryTree(TreeNode root) {
            if(root==null) return 0;
            LinkedList<TreeNode> queue=new LinkedList<TreeNode>();
            LinkedList<Integer> indexQueue =new LinkedList<Integer>();
            queue.add(root);
            indexQueue.add(1);
            int maxWidth=1;
            //如果进入了循环,说明该队列中还有结点,则将该队首出队
            while (!queue.isEmpty()){
                int count=queue.size();//每一层的元素节点个数
                int left=indexQueue.peek();//队列的第一个元素的索引,也就是该层最左边的那个索引
                //每一层
                while (count>0){
                    TreeNode node = queue.poll();//当前节点
                    Integer index = indexQueue.poll();//当前索引
                    if(node.left != null){
                       queue.add(node.left);
                       indexQueue.add(index * 2);//左节点的索引是2*k
                    }
                    if (node.right != null) {
                       queue.add(node.right);
                       indexQueue.add(index * 2 + 1);//右节点的位置是 2*k+1
                    }
                    count--;
                    if(count==0)
                      maxWidth = Math.max(maxWidth, index - left + 1); //每层遍历完成后计算该层的最大宽度(队列最后一个元素索引-队列的最前面元素索引+1)
                }       
            }
            return maxWidth;
    }
}

3.判断是否是二叉搜索树

判断二叉搜索树:二叉搜索树的特征:左节点小于右节点。可以使用中序遍历,中序遍历绝对是递增的

  	//中序遍历 看是否是递增
    long preValue= Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if(root==null) return true;
        boolean left=isValidBST(root.left);
        boolean mid = false;
        if(root.val>preValue) {
            mid=true;
            preValue=root.val;
        }
        boolean right= isValidBST(root.right);
        return left && mid && right;
    }

4.判断是否是平衡二叉树

平衡二叉树: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

思想:后序遍历,对于当前遍历到的节点,先递归地判断其左右子树是否平衡,再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的,则返回其高度(高度一定是非负整数),否则返回 -1。如果存在一棵子树不平衡,则整个二叉树一定不平衡。

	 public boolean isBalanced(TreeNode root) {
        if(root == null) return true;//空树就是平衡的
        return getMaxHeight(root)>=0;
    }
 
     public int getMaxHeight(TreeNode node){
         if(node==null) return 0;//空树当然是平衡的
         int leftHeight=0,rightHeight=0;
         if(node.left != null)
            leftHeight=getMaxHeight(node.left);//获得左子树的高度
         if(node.right != null)
            rightHeight=getMaxHeight(node.right);//获得右子树的高度

         //如果左子树高度为-1或者右子树为-1或者他们的高度差大于1,自己返回-1给上一级  
         if(leftHeight == -1 || rightHeight==-1 ||Math.abs(leftHeight-rightHeight)>1)
            return -1;
         //否则就返回当前子树的最大高度
         return  leftHeight > rightHeight ? leftHeight+1:rightHeight+1;  


     }

5.二叉树的最近公共祖先(重点)

两个节点的最近公共祖先

  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //如果当前节点为空,直接返回 如果当前节点等于其中一个节点了,直接返回当前节点
        if(root == null || root==p || root==q) return root;

        TreeNode left=lowestCommonAncestor(root.left,p,q);//向左边询问节点值
        TreeNode right=lowestCommonAncestor(root.right,p,q);//向右边询问节点

        //当左右返回的都不为空 返回当前节点
        //因为搜索的时候,如果有一方没搜索到,就返回的null,当两方都搜索到了,则当前节点绝对是他们的最近祖先
        if(left !=null && right !=null)
            return root;
        //不都为空的时候 返回不为空的那个,有可能都为null    
        return left!=null ? left:right;
    }

6.二叉搜索树的下一个节点

下一个节点:所谓 该节点的后继节点,就是中序遍历中,比 p 大的下一个

思想:如果 p 大于等于当前节点的值,说明后继节点一定在右子树中

​ 如果 p 小于当前节点的值,说明后继节点一定在左子树或自己就是,递归调用 左子树,如果是空的,说明当前节点就是答案。如果不是空的,则说明在 左子树中已经找到合适的答案,直接返回即可。

public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if(root == null) return null;
        // 当前节点值小于等于目标值,那么当前目标值的后继者必然在右子树
        if (p.val >= root.val) 
            return inorderSuccessor(root.right, p);

        // 否则结果有可能是当前节点,或者在当前节点的左子树中
        // 那么先去左子树找一下试试,找不到的话返回当前节点即是结果
        TreeNode node = inorderSuccessor(root.left, p);
        return node == null ? root : node;
    }

7.另一个树的子树

判断是否是子树问题:一个树是另一个树的子树 则三种情况:

  • 要么这两个树相等

  • 要么这个树是另外一个的左子树

  • 要么这个树是另外一个的右子树

    满足其中一个条件即可

    思想:前序遍历dfs,先判断当前节点是不是一样,如果不一样,则查找左子树,然后查找右子树。如果当前节点一样了,则调用isSameTree方法判断剩下两棵树的节点是否一样。

 		//这个函数相当于进行了dfs找到第一个一样的节点 然后调用isSameTree判断两棵树是不是一模一样
       public boolean isSubtree(TreeNode s, TreeNode t) {
            // 我s都遍历完了。你居然还没匹配上。那就返回false
            if (s==null) return false;
            boolean sameFlag=isSameTree(s,t);//判断两个数是不是一样
            boolean leftSubtree=isSubtree(s.left,t);//判断是不是左子树
            boolean rightSubTree=isSubtree(s.right,t);//判断是不是右子树
            return  sameFlag || leftSubtree || rightSubTree;//满足一个条件即可
        }

    public boolean isSameTree(TreeNode s,TreeNode t){
            if (s==null && t == null)  return true;  // 同时为空 说明树一起到底,两树相同 
            if (s == null || t == null) return false;  // 当有一个不为空(有可能两个都不为空)
            // 说明两个都不为空
            // 先序遍历 自己--左 -- 右
            if (s.val != t.val) return false;//如果两个值不一样 则返回false
            //如果值一样 则分别向左右子树询问是否一样
            boolean left=isSameTree(s.left,t.left);
            boolean right=isSameTree(s.right,t.right);
            return  left && right;
        }

8. 重建二叉树

重建二叉树:根据二叉树的前序遍历和中序遍历的结果,重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

前序遍历的第一个值为根节点的值,使用这个值将中序遍历结果分成两部分,左部分为树的左子树中序遍历结果,右部分为树的右子树中序遍历的结果。然后分别对左右子树递归地求解。

 // 缓存中序遍历数组每个值对应的索引
    private Map<Integer, Integer> indexForInOrders = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++)
            indexForInOrders.put(inorder[i], i);
        //然后开始操作前序遍历的数组
        return getTree(preorder, 0, preorder.length - 1, 0);

    }
    private TreeNode getTree(int[] pre, int left, int right, int inL) {
        if (left > right)
            return null;
        TreeNode root = new TreeNode(pre[left]);
        int inIndex = indexForInOrders.get(root.val);
        int leftTreeSize = inIndex - inL;
        root.left = getTree(pre, left + 1, left + leftTreeSize, inL);
        root.right = getTree(pre, left + leftTreeSize + 1, right, inL + leftTreeSize + 1);
        return root;
    }

9. 二叉树的镜像(重点)

二叉树的镜像

   public TreeNode mirrorTree(TreeNode root) {
        if(root == null) return null;
        //借助个临时节点来避免覆盖后找不到左(右)节点。
        TreeNode tmpNode = root.left;
        root.left=mirrorTree(root.right);
        root.right=mirrorTree(tmpNode);
        return root;
    }

10.二叉树是否对称

二叉树是否对称

 public boolean isSymmetric(TreeNode root) {
        if(root == null) return false;
        return getIsSymmetric(root.left,root.right);
    }
    public static boolean getIsSymmetric(TreeNode tree1, TreeNode tree2) {
        //当两个都是空 为true
        if(tree1 == null && tree2==null) return false;
        //当有一个为空 为false
        if(tree1 == null ||  tree2 ==null) return false;
        //值不相等 也为false
        if(tree1.val != tree2.val) return false;
        //当两个都不为空 继续调用,注意这里应该判断左右节点的对称部分 如果左节点传左子树 那么右节点就需要传右子树
        return getIsSymmetric(tree1.left,tree2.right) && getIsSymmetric(tree1.right,tree2.left);
    }