字节高频50题103. 二叉树的锯齿形层序遍历 199. 二叉树的右视图 (都是bfs) 93. 复原 IP 地址回溯,dfs

/**
 * 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;
 *     }
 * }
 */
 /**
 解题思路：首先我们发现是层序遍历的改变，也就是说bfs，我们先写层序遍历
  */
class Solution {
    List<List<Integer>> res_lst= new LinkedList<>();;
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        //层序遍历
        bfs(root);
        return res_lst;
        
    }
    private void bfs(TreeNode root){
        //奇偶判断添加顺序
        boolean flag = true;  //代表从左到右
        //队列
        Queue<TreeNode> queue = new LinkedList<>();
        if(root != null)
            queue.add(root);

        while(!queue.isEmpty()){
            //当前层的个数
            int size = queue.size();
            //数组
            LinkedList<Integer> levl_ary = new LinkedList<>();
            //这是每一层的，我们要根据是第几层来进行排序
            while(size!=0){
                //取出节点
                TreeNode node = queue.poll();

                if(flag)
                    levl_ary.addLast(node.val);
                else
                    levl_ary.addFirst(node.val);
                    
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
                size--;
            }
            //对当前层取反
            flag = !flag;
            //存入到res中
            res_lst.add(levl_ary);
        }
    }
}

/**
 * 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 {
    List<Integer> res = new LinkedList<>();
    public List<Integer> rightSideView(TreeNode root) {
        bfs(root);
        return res;
    }
    private void bfs(TreeNode root){
        //队列
        Queue<TreeNode> queue = new LinkedList<>();
        if(root == null)
            return;
        queue.add(root);
        while(!queue.isEmpty()){
            //就当前层的个数
            int size = queue.size();
            //遍历当前层的节点,但是因为我们只要每一层的最右边节点，所以我们每次留最后一个
            while(size!=0){
                TreeNode node =queue.poll();
                if(size == 1)  
                    res.add(node.val); 
                if(node.left != null)           
                    queue.add(node.left);
                if(node.right!=null)
                    queue.add(node.right);
                size--;
            }
        }
    }
}

/**
解题思想：分成4个整数，每组包含1~3位的数 ，找所有的结果：那就是回溯，通过dfs
 */
class Solution {
    //4段
    static final int SEG_COUNT=4;
    //每段所放值
    int[] segments = new int[SEG_COUNT];
    //返回的数组
    List<String> res = new LinkedList<>();

    public List<String> restoreIpAddresses(String s) {
        dfs(s,0,0);
        return res;
    }
    private void dfs(String s, int segId , int segStart){
        //先写头，如果找到了 4 段 IP 地址并恰好遍历完了字符串，那就是其中一种答案
        if(segId == SEG_COUNT){
            if(segStart == s.length()){
                StringBuffer isIpAds = new StringBuffer();
                for(int i=0 ; i<SEG_COUNT ; i  ){
                    isIpAds.append(segments[i]);
                    if(i != SEG_COUNT-1)
                        isIpAds.append('.');
                }
                res.add(isIpAds.toString());
            }
            return;
        }
        //递归头写完了，开始写一写特殊情况，如果没有找到4段就遍历完了，则返回
        if(segStart == s.length())
            return;
        //如果为0
        if(s.charAt(segStart) == '0'){
            segments[segId] = 0;
            dfs(s,segId 1,segStart 1);
        }
        //剩下就是正常情况求每段中的值
        int segVal = 0;
        for(int segEnd = segStart ; segEnd<s.length() ; segEnd  ){
            segVal = segVal * 10   (s.charAt(segEnd)-'0');
            if(segVal>0 && segVal<=0xFF){ //已经有了一个字段为0的情况，所以要将0的范围除去
                segments[segId] = segVal;
                dfs(s,segId 1 , segEnd 1);
            }else{
                break;
            }
        }
    }
}

这篇好文章是转载于：学新通技术网