LeetCode-102,103,107,111总结

系统管理员 2022-08-20 13:19 196阅读 0赞

--------------------

**102**. Binary Tree Level Order Traversal  
Problem:

> Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).  
> For example:  
> Given binary tree \{3,9,20,\#,\#,15,7\},
> 
>     3    
>           / \   
>          9  20
>            /  \    
>           15   7
> 
> return its level order traversal as:
> 
> \[  
> \[3\],  
> \[9,20\],  
> \[15,7\]  
> \]  
> Anwser：

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        
        public List<List<Integer>> levelOrder(TreeNode root) {
            List<List<Integer>> result = new LinkedList<List<Integer>>();
            if(root==null) return result;
            Queue<TreeNode> nodes = new LinkedList<TreeNode>();
            nodes.add(root);
            //isEmpty(),size()是collection接口的函数，Queue、List、Set等接口是collection的子接口
            while(!nodes.isEmpty()){
                LinkedList<Integer> innerList = new LinkedList<Integer>();
                int size = nodes.size();
                for(int i=0;i<size;i++){
                    TreeNode current = nodes.poll();
                    //*
                    innerList.add(current.val);
                    //
                    if(current.left!=null) nodes.add(current.left);
                    if(current.right!=null) nodes.add(current.right);
                }
                result.add(innerList);
            }
            return result;
        }
    }

--------------------

**103**. Binary Tree Zigzag Level Order Traversal  
Problem：

> Given a binary tree, return the zigzag level order traversal of its  
> nodes’ values. (ie, from left to right, then right to left for the  
> next level and alternate between).
> 
> For example: Given binary tree \{3,9,20,\#,\#,15,7\},

3    
        / \   
       9  20
         /  \    
        15   7

> return its zigzag level order traversal as:  
> \[  
> \[3\],  
> \[20,9\],  
> \[15,7\]  
> \]

Anwser：

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> result=new LinkedList<List<Integer>>();
            if (root==null) return result;
            Queue<TreeNode> q = new LinkedList<TreeNode>();
            int level=0;
            q.add(root);
            while(!q.isEmpty()){
               List<Integer> innerlist =new LinkedList<Integer>();
               int size = q.size();
               for(int i=0;i<size;i++){
                   TreeNode temp = q.poll();
                   //此处有差别
                   if(level%2==1) innerlist.add(0,temp.val);
                   else innerlist.add(temp.val);
                   //
                   if(temp.left!=null) q.add(temp.left);
                   if(temp.right!=null) q.add(temp.right);
               }
               level++;
               result.add(innerlist);
            }
            return result;
        }
    }

--------------------

**107**. Binary Tree Level Order Traversal II  
Problem:

> Given a binary tree, return the bottom-up level order traversal of its  
> nodes’ values. (ie, from left to right, level by level from leaf to  
> root).
> 
> For example: Given binary tree \{3,9,20,\#,\#,15,7\},

3   
          / \   
         9  20
            / \    
           15  7

> return its bottom-up level order traversal as:  
> \[  
> \[15,7\],  
> \[9,20\],  
> \[3\]  
> \]

Anwser:

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        
        public List<List<Integer>> levelOrderBottom(TreeNode root) {
            List<List<Integer>> result = new LinkedList<List<Integer>>();
            if(root==null) return result;
            Queue<TreeNode> nodes = new LinkedList<TreeNode>();
            nodes.add(root);
            //isEmpty(),size()是collection接口的函数，Queue、List、Set等接口是collection的子接口
            while(!nodes.isEmpty()){
                LinkedList<Integer> innerList = new LinkedList<Integer>();
                int size = nodes.size();
                for(int i=0;i<size;i++){
                    TreeNode current = nodes.poll();
                    innerList.add(current.val);
                    if(current.left!=null) nodes.add(current.left);
                    if(current.right!=null) nodes.add(current.right);
                }
                //此处有不同
                result.add(0,innerList);
                //
            }
            return result;
        }
    }

--------------------

**111**. Minimum Depth of Binary Tree My Submissions Question  
Problem:

> Given a binary tree, find its minimum depth.  
> The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.  
> Anwser:

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        
        public int minDepth(TreeNode root) {
            if(root==null) return 0;
            //注意这个题的意思，求根节点到最近的叶子节点之间的距，如［1，2］最小深度为2而不是1
            else if(root.left==null||root.right==null) return Math.max(minDepth(root.left),minDepth(root.right))+1;
            else return Math.min(minDepth(root.left),minDepth(root.right))+1;
        }
    }

分析：  
这均属于层序遍历（BFS），都利用了队列，只是在返回结果时有不同的顺序要求，由于列表自带list.add(index,value)这个函数（详解见[http://blog.csdn.net/u010305706/article/details/50764317][http_blog.csdn.net_u010305706_article_details_50764317]），所以利用这个函数实现省了不少事。

当然BFS可以利用DFS实现，如102题用DFS实现代码如下：

public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
        if (root == null) return ans;
        traverse(ans, root, 0);
        return ans;
    }
    
    private void traverse (ArrayList<ArrayList<Integer>> ans, TreeNode node, int level) {
        if (node == null) return;
        if (ans.size() >= level + 1) 
            ans.get(level).add(node.val);
        else {
            ArrayList<Integer> temp = new ArrayList<Integer>();
            temp.add(node.val);
            ans.add(temp);
        }
        traverse(ans, node.left, level + 1);
        traverse(ans, node.right, level + 1);
    }

[http_blog.csdn.net_u010305706_article_details_50764317]: http://blog.csdn.net/u010305706/article/details/50764317