代码随想录–二叉树

二叉树

二叉树--二叉树的递归遍历

题目:

  • 144.二叉树的前序遍历(opens new window)

  • 145.二叉树的后序遍历(opens new window)

  • 94.二叉树的中序遍历

    题解:

    前序遍历

    class Solution {
        public List<Integer> preorderTraversal(TreeNode root) {
            List<Integer> result = new ArrayList<Integer>();
            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);
        }
    }
    

    中序遍历

    class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> res = new ArrayList<>();
            inorder(root, res);
            return res;
        }
    
        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> res = new ArrayList<>();
            postorder(root, res);
            return res;
        }
    
        void postorder(TreeNode root, List<Integer> list) {
            if (root == null) {
                return;
            }
            postorder(root.left, list);
            postorder(root.right, list);
            list.add(root.val);             // 注意这一句
        }
    }
    

    解析:递归遍历,前序遍历:根左右遍历。中序遍历:左根右。后续遍历:左右根。

二叉树--二叉树的迭代遍历

题目:

题解:

前序遍历

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> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()){
           if (cur != null){
               stack.push(cur);
               cur = cur.left;
           }else{
               cur = stack.pop();
               result.add(cur.val);
               cur = cur.right;
           }
        }
        return result;
    }
}

后序遍历:

class Solution {
    public List<Integer> postorderTraversal(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.left != null){
                stack.push(node.left);
            }
            if (node.right != null){
                stack.push(node.right);
            }
        }
        Collections.reverse(result);
        return result;
    }
}

解析:

前序遍历:

前序遍历如图所示:

二叉树前序遍历(迭代法)

中序遍历如图所示:

二叉树中序遍历(迭代法)

后续遍历类似。

二叉树--二叉树的层序遍历

题目:力扣题目链接

给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。

示例 1:

输入:root = [3,9,20,null,null,15,7]
输出:[[3],[9,20],[15,7]]
示例 2:

输入:root = [1]
输出:[[1]]
示例 3:

输入:root = []
输出:[]

题解:

/**
 * 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;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> resList= new ArrayList<List<Integer>>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        check(root);
        return resList;
    }
    public void check(TreeNode node){
        if(node ==null){
            return;
        }
       Queue<TreeNode> que= new LinkedList<TreeNode>();
       que.offer(node);
       while(!que.isEmpty()){
         List<Integer> itemList= new ArrayList<Integer>();
         int len=que.size();
         while(len>0){
          TreeNode tmpNode = que.poll();
          itemList.add(tmpNode.val); 
            if(tmpNode.left!=null){
                que.offer(tmpNode.left); 
            }
            if(tmpNode.right!=null){
                que.offer(tmpNode.right);
            }
            len--;
         } 
         resList.add(itemList);
       }

    }
}

解析:102二叉树的层序遍历

借助队列:

用一个list集合嵌套一个list集合里面包含每一层的数值,借助队列,把根元素加到队列里面,统计队列里面元素个数,弹出一个元素,加到tmplist集合里面,再把弹出元素的左右节点(如果有)加入队列,len--,直到把原始队列里面元素全部弹完,len=0.然后把这一层的元素加到resList队列里面,不断遍历循环,直到队列为空结束,最后返回reslist,实现二叉树的层序遍历。

二叉树--翻转二叉树

题目:

力扣题目链接

翻转一棵二叉树。

226.翻转二叉树

题解:

迭代法:

/**
 * 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;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null){
            return null;
        }
       ArrayDeque<TreeNode> deque= new ArrayDeque<>();
       deque.offer(root);
       while(!deque.isEmpty()){
       int size=deque.size();
       while(size-->0){
          TreeNode node= deque.poll();
          swap(node);
          if(node.left!=null){
              deque.offer(node.left);
          }
          if(node.right!=null){
              deque.offer(node.right);
          }
       }
       }
       return root;
    }

    public void swap(TreeNode root){
        TreeNode t=root.left;
        root.left=root.right;
        root.right=t;
    }
}

解析:

ArrayDeque的介绍:

ArrayDeque是 Deque接口的一个实现,使用了可变数组,所以没有容量上的限制。同时, ArrayDeque是线程不安全的,在没有外部同步的情况下,不能再多线程环境下使用。
ArrayDeque是 Deque的实现类,可以作为栈来使用,效率高于 Stack;也可以作为队列来使用,效率高于 LinkedList。
ArrayDeque 是 Java 集合中双端队列的数组实现,双端队列的链表实现(LinkedList)
需要注意的是, ArrayDeque不支持 null值。

用ArrayDeque当作一个队列,先把根节点放入队列中,当队列不为空,且队列中元素大于0时,先弹出一个元素,把这个元素的左右子树进行交换,当存在左子树或右子树的情况,则依次加入队列中

递归法:

/**
 * 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;
 *     }
 * }
 */
class Solution {
     public TreeNode invertTree(TreeNode root) {
        if(root==null){
            return null;
        }
     invertTree(root.left);
     invertTree(root.right);
     swapChildren(root);
        return root;
    }

    private void swapChildren(TreeNode root) {
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
    }
}

解析:当根节点不存在时返回null,存在则把根的左子树放入递归操作,然后在把右子树放入递归操作,接着执行交换的方法。递归完成后,也完成了反转的逻辑。

二叉树--对称二叉树

题目:力扣题目链接

给定一个二叉树,检查它是否是镜像对称的。

101. 对称二叉树

题解:

递归法:

/**
 * 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;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return compare(root.left,root.right);
    }
    private boolean compare(TreeNode left,TreeNode right){
        if(left==null&&right!=null){
            return false;
        }
        if(left!=null&&right==null){
            return false;
        }
        if(left==null&&right==null){
            return true;
        }
        if(left.val!=right.val){
            return false;
        }
        //比较外侧
        boolean compareOutside= compare(left.left,right.right);
        //比较内测
        boolean compareInside= compare(left.right,right.left);
        return compareOutside&&compareInside;
    }
}

解析:把不对称或对称的情况进行判断返回,分别递归比较外侧和内测,最后返回内外侧即可。

101. 对称二叉树1

迭代法:使用双端队列,相当于两个栈

/**
 * 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;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
    Deque<TreeNode> deque = new LinkedList<>();
    deque.offerFirst(root.left);
    deque.addLast(root.right);
    while(!deque.isEmpty()){
       TreeNode leftNode= deque.pollFirst();
       TreeNode rightNode=deque.pollLast();
       if(leftNode==null&&rightNode==null){
           continue;
       }
        if(leftNode==null||rightNode==null||leftNode.val!=rightNode.val){
            return false;
        }
        deque.offerFirst(leftNode.left);
        deque.offerFirst(leftNode.right);
        deque.offerLast(rightNode.right);
        deque.offerLast(rightNode.left);
    }
    return true;
    }
}

解析:双端队列往头插入根节点的左节点,往尾插入根节点的右节点,在栈不为空的情况下,分别从两端弹出,然后判断对称条件进行返回,最后往栈里头部插入左节点的左节点,再往头部插入左节点的右节点,继续往尾部插入右节点的右节点,最后往尾部插入右节点的左节点,使弹出的两个元素全为外侧或全为内侧进行检查是否为轴对称。,当栈为空时,表示二叉树中所有元素进行了轴对称检查。

迭代法:使用普通队列:

public boolean isSymmetric3(TreeNode root) {
        Queue<TreeNode> deque = new LinkedList<>();
        deque.offer(root.left);
        deque.offer(root.right);
        while (!deque.isEmpty()) {
            TreeNode leftNode = deque.poll();
            TreeNode rightNode = deque.poll();
            if (leftNode == null && rightNode == null) {
                continue;
            }
//            if (leftNode == null && rightNode != null) {
//                return false;
//            }
//            if (leftNode != null && rightNode == null) {
//                return false;
//            }
//            if (leftNode.val != rightNode.val) {
//                return false;
//            }
            // 以上三个判断条件合并
            if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
                return false;
            }
            // 这里顺序与使用Deque不同
            deque.offer(leftNode.left);
            deque.offer(rightNode.right);
            deque.offer(leftNode.right);
            deque.offer(rightNode.left);
        }
        return true;
    }

解析:同上面

二叉树--二叉树的最大深度

题目:力扣题目链接

给定一个二叉树,找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例:
给定二叉树 [3,9,20,null,null,15,7],

3

/
9 20
/
15 7
返回它的最大深度 3 。

题解:递归法:

class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
       int leftDepth= maxDepth(root.left);
       int rightDepth = maxDepth(root.right);
       return Math.max(leftDepth,rightDepth)+1;
    }
}

解析:如果根节点为空最大深度为0,根节点不为空时,分别递归左子树和右子树,最后选择深度较大者加上根节点则为二叉树的最大深度。

题解:迭代法:

/**
 * 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;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
       if(root==null){
           return 0;
       }
      Deque<TreeNode> deque= new LinkedList();
      deque.offer(root);
      int depth=0;
      while(!deque.isEmpty()){
          int size=deque.size();
          depth++;
          for(int i=0;i<size;i++){
              TreeNode node=deque.poll();
              if(node.left!=null){
                  deque.offer(node.left);
              }
              if(node.right!=null){
                  deque.offer(node.right);
              }
          }
      }
      return depth;
    }
}

解析:无根节点时,深度为0。有根节点,用双端队列解决此题,先把根节点放入队列中,当队列不为空时,深度加一

遍历出队列的大小,遍历size次,当左节点不为空时,队列中加入左节点,右节点不为空时,队列加入右节点。不断循环遍历直到队列为空,返回深度。

二叉树--N叉树的最大深度

题目:力扣题目链接(opens new window)

给定一个 n 叉树,找到其最大深度。

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

例如,给定一个 3叉树 :

559.n叉树的最大深度

我们应返回其最大深度,3

题解:递归法:

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
    public int maxDepth(Node root) {
        if(root==null){
            return 0;
        }
        int depth=0;
        if(root.children != null){
            for(Node child:root.children){
                depth=Math.max(depth,maxDepth(child));
            }
        }
    return depth+1;
    }
}

解析:根节点为空返回0,不为空,当根的子节点不为空时,遍历出每个节点,把这个节点进行递归,比较出最大深度。

迭代法:

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
    public int maxDepth(Node root) {
    if(root==null){
        return 0;
    }
    int depth=0;
    Queue<Node> que= new LinkedList<>();
    que.add(root);
    while(!que.isEmpty()){
        depth++;
        int len=que.size();
        while(len>0){
           Node node= que.poll();
           for (int i = 0; i < node.children.size(); i++)
                    if (node.children.get(i) != null) 
                   que.offer(node.children.get(i));
                   len--;
               }
           }
                 return depth;
        }
    }

二叉树--二叉树的最小深度

题目:力扣题目链接(opens new window)

给定一个二叉树,找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

示例:

给定二叉树 [3,9,20,null,null,15,7],

111.二叉树的最小深度1

返回它的最小深度 2

题解:递归法:

/**
 * 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;
 *     }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
       int leftDepth= minDepth(root.left);
       int rightDepth=minDepth(root.right);
       if(root.left==null){
           return rightDepth+1;
       }
       if(root.right==null){
           return leftDepth+1;
       }
       return Math.min(leftDepth, rightDepth) + 1;
    }
}

解析:递归遍历根节点的左节点和右节点,如果根的左节点为空,则深度为右节点的深度加1,如果根的右节点为空,则深度为左节点深度加1

题解:迭代法:

/**
 * 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;
 *     }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
       if(root==null){
           return 0;
       }
      Deque<TreeNode> deque= new LinkedList<>();
      deque.offer(root);
      int depth=0;
      while(!deque.isEmpty()){
         int size= deque.size();
         depth++;
         for(int i=0;i<size;i++){
             TreeNode poll=deque.poll();
             if(poll.left==null&&poll.right==null){
                 return depth ;
             }
             if(poll.left!=null){
                 deque.offer(poll.left);
             }
             if(poll.right!=null){
                 deque.offer(poll.right);
             }
         }
      }
      return depth;
    }
}

题解:使用队列解题,先把根节点放入队列中,声明出深度,当队列不为空时,深度加1,遍历放入队列中的元素,弹出一个元素,如果发现是叶子节点,则返回该深度,如果发现弹出节点poll的左节点不为空,则加入队列里面,右节点不为空则加到队列里面,直到遍历完成,返回对应的最小深度。

二叉树--完全二叉树的节点个数

题目:力扣题目链接(opens new window)

给出一个完全二叉树,求出该树的节点个数。

示例 1:

  • 输入:root = [1,2,3,4,5,6]
  • 输出:6

示例 2:

  • 输入:root = []
  • 输出:0

示例 3:

  • 输入:root = [1]
  • 输出:1

提示:

  • 树中节点的数目范围是[0, 5 * 10^4]

  • 0 <= Node.val <= 5 * 10^4

  • 题目数据保证输入的树是 完全二叉树

    img

题解:递归法

/**
 * 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;
 *     }
 * }
 */
class Solution {
    public int countNodes(TreeNode root) {
        if(root==null){
            return 0;
        }
        return countNodes(root.left)+countNodes(root.right)+1;
    }
}

解析:递归根的左节点和根的右节点得出最后的节点个数再加1即可

题解:迭代法

/**
 * 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;
 *     }
 * }
 */
class Solution {
    public int countNodes(TreeNode root) {
        if(root==null){
            return 0;
        }
       Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int result=0;
        while(!queue.isEmpty()){
            int size = queue.size();
            while(size-->0){
               TreeNode node= queue.poll();
               result++;
               if(node.left!=null){
                   queue.offer(node.left);
               }
               if(node.right!=null){
                   queue.offer(node.right);
               }
            }
        }
      return result;
    }
}

解析:利用迭代法,使用一个队列,队列中先加入根节点,定义总数变量,当队列不为空时,,先拿到队列的个数,当队列个数大于1时,先让size-1,弹出一个元素,节点个数加1,当弹出的节点的左节点不为空时,则加入队列中,当弹出节点右节点不为空时,则加入到队列中,不断的去迭代,最后统计出最后的个数。

二叉树--平衡二叉树

题目:力扣题目链接(opens new window)

给定一个二叉树,判断它是否是高度平衡的二叉树。

本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

110.平衡二叉树

返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

110.平衡二叉树1

/**
 * 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;
 *     }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        return getHeight(root)!=-1;
    }
    private int getHeight(TreeNode root){
        if(root==null){
            return 0;
        }
        int LeftHeight=getHeight(root.left);
        if(LeftHeight==-1){
            return -1;
        }
        int RightHeight = getHeight(root.right);
        if(RightHeight==-1){
            return -1;
        }
        if(Math.abs(LeftHeight-RightHeight)>1){
            return -1;
        }
        return Math.max(LeftHeight,RightHeight) + 1;
    }
}

解析:首先设计当获取二叉树的高度不是-1时,则返回正确,否则不满足要求。编写函数,首先如果根节点也没有,直接返回0,且满足要求。然后再把根的递归查左节点的高度,如果高度为-1,则不满足平衡二叉树,直接返回-1,根的右节点也是这样。接着如果左节点的高度和右节点的高度相差超过了1,则不是高度平衡的二叉树返回-1。否则是一个高度平衡二叉树,返回对应的高度。

二叉树--二叉树的所有路径

题目:

力扣题目链接(opens new window)

给定一个二叉树,返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

示例:

257.二叉树的所有路径1

题解:递归法

/**
 * 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;
 *     }
 * }
 */
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
      List<String> res= new ArrayList<>();//最终要存的
      if(root==null){
          return res;
      }
      List<Integer> paths= new ArrayList<>();//结果路径
      traversal(root,res,paths);
      return res;
    }
    public void traversal(TreeNode root,List<String> res,List<Integer> paths){
        paths.add(root.val);
        if(root.left==null&&root.right==null){
           StringBuilder sb= new StringBuilder();
           for(int i=0;i<paths.size()-1;i++){
               sb.append(paths.get(i)).append("->");
           }
           sb.append(paths.get(paths.size()-1));
           res.add(sb.toString());
           return;
        }
        if (root.left != null) { 
            traversal(root.left, res,paths);
            paths.remove(paths.size() - 1);// 回溯
        }
        if (root.right != null) { 
            traversal(root.right, res,paths); 
            paths.remove(paths.size() - 1);// 回溯
        }
    }
}

解析:定义一个最终存的list和结果路径的list,先把根的值放入结果路径的list,当根的左节点和右节点都为空时,定义一个StringBuilder开始追加内容,把一个路径上的前size-1个节点放入paths里面并且每个节点加上->,最后额外加上最后一个节点,把这一整个路径放入最终集合res里面,返回即可,如果root的左节点或者右节点不为空时,则开始递归,并且回溯,递归一个回溯一个。最终完成了返回从根节点到叶子节点的路径。

原文链接:https://www.cnblogs.com/zixiangm/p/17260297.html

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:代码随想录–二叉树 - Python技术站

(0)
上一篇 2023年4月18日
下一篇 2023年4月18日

相关文章

  • 详解二分查找算法原理与使用方法

    二分查找算法,又称折半查找算法,是一种高效的查找算法。它的基本思想是将查找区间从中间进行分割,再根据目标值与中间值的大小关系选择下一次查找的区间,从而逐步缩小查找范围,直到找到目标值或无法分割为止。这种算法的时间复杂度是 $O(\log n)$,非常适合于大型数据集的查找。 作用 二分查找算法适用于有序数组中的查找操作,可以快速定位数组中特定元素的位置,比如…

    算法 2023年3月27日
    00
  • 用Python制作简单的朴素基数估计器的教程

    下面是详细讲解“用Python制作简单的朴素基数估计器的教程”的完整攻略。 1. 什么是朴素贝叶斯估计器 朴素贝叶斯估计器是一种基于贝叶斯定理和特征条件独立假设的概率估计方法。它通过计算每个类别的先验概率和每个特征在给定类别下的条件概率来进行概率估计。朴素贝叶斯估计器具有计算简单、速度快、可扩展性好等优点,因此在实际应用中得到了广泛的应用。 2. 朴素贝叶斯…

    python 2023年5月14日
    00
  • C语言数据结构时间复杂度及空间复杂度简要分析

    C语言数据结构时间复杂度及空间复杂度简要分析 什么是时间复杂度和空间复杂度? 在分析算法和数据结构的性能时,时间复杂度和空间复杂度是必须考虑的因素。 时间复杂度:衡量算法执行时间所需的资源,也就是算法的速度。通常使用“大O符号”来表示时间复杂度,例如O(1)、O(n)、O(nlogn)等。 空间复杂度:衡量算法使用的内存资源,也就是算法的空间利用率。通常使用…

    数据结构 2023年5月17日
    00
  • Python实现的基于优先等级分配糖果问题算法示例

    以下是关于“Python实现的基于优先等级分配糖果问题算法示例”的完整攻略: 简介 糖果分配问题是一个经典的问题,通常涉及到将一定数量的糖果分配给一组孩子。在这个问题中,每个孩子都有一个优先级,我们需要按照优先级分配糖果,同时确保每个孩子至少分配到一个糖果。本教程将介绍如何使用Python实现基于优先等级分配糖果问题的算法。 步骤 1. 定义函数 首先,我们…

    python 2023年5月14日
    00
  • Python查找算法之插补查找算法的实现

    Python查找算法之插补查找算法的实现 插补查找算法是一种高效的查找算法,它是在二分查找算法的基础上进行改进的。插补查算法的基本思想是根据查找值在查找表中的位置进行插值计算,从而确定下一次查找的位置。本文将详细讲解Python查找算法之插补查找算法的实现,包括算法原理、Python实现过程和示例。 算法原理 插补查找算法是一基于二分查找法的改进算法,它的基…

    python 2023年5月13日
    00
  • C语言结构体struct详解

    C语言结构体struct详解 什么是结构体? 在C语言中,结构体是一种用户自定义的数据类型,它可以将不同的数据类型组合在一起形成一个新的数据类型。结构体主要由结构体名、成员和符号构成。 使用结构体可以方便地定义一些复杂的数据类型,例如表示一个学生信息的数据类型,可以包括姓名、学号、性别、年龄等信息。 结构体的定义和声明 结构体的定义通常放在函数外部,以便在整…

    数据结构 2023年5月17日
    00
  • Python实现的计算马氏距离算法示例

    Python实现的计算马氏距离算法示例 马氏距离是一种常用的距离度量方法,它可以用于计算两个随机向量之间的距离。在Python中,可以使用NumPy库实现计算马氏距离算法。本文将详细讲解Python实现计算马氏距离算法的完整攻略,包括算法原理、Python实现过程和示例。 算法原理 马氏距离是一种常用的距离度量方法,可以用于计算两个随机向量之间的距离。马氏距…

    python 2023年5月14日
    00
  • C语言数据结构之复杂链表的拷贝

    C语言数据结构之复杂链表的拷贝 什么是复杂链表 在了解如何拷贝复杂链表之前,首先需要知道什么是复杂链表。复杂链表是由多个节点组成的链表,每个节点除了包含普通链表节点的值和指向下一个节点的指针外,还包含一个指向链表中的任意一个节点的指针。因此,每个节点有两个指针:一个指向下一个节点,一个指向任意一个节点。 复杂链表示意图如下: +—+ +—+ +—…

    数据结构 2023年5月17日
    00
合作推广
合作推广
分享本页
返回顶部