二叉树层序遍历 ii

/*
坑：树为空时，不能返回null，也要返回一个空ArrayList。
用BFS。
记下一层节点数，以及当前位置，来判断是否为该层的最后一个节点。
遍历到当前层最后一个节点时，将当前list加到一个栈里面。
最后把栈里面的list弹出。
ps：进入下一层时，不能直接清空当前的list，栈里面的引用一直指向当前的list，
所以必须指向一个新的list对象。
别人的代码思想更简单。
*/
import java.util.*;
public class Solution {
    private Stack<ArrayList<Integer>> stack = new Stack<>();
    private Queue<TreeNode> queue = new LinkedList<>();

    public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        if (root == null) return ans;
        bfs(root);
        while(!stack.empty()) {
            ans.add(stack.pop());
        }
        return ans;
    }

    public void bfs(TreeNode root) {
        int cnt = 0;   //下一层节点的个数。
        int tmp = 1;   //本层节点的个数。
        int loc = 0;   //当前节点的位置。
        queue.offer(root);
        ArrayList<Integer> list = new ArrayList<>();
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            loc++;
            list.add(node.val);
            if (node.left != null) {
                queue.offer(node.left);
                cnt++;
            }
            if (node.right != null) {
                queue.offer(node.right);
                cnt++;
            }
            if (loc == tmp) {
                loc = 0;
                tmp = cnt;
                cnt = 0;
                stack.push(list);
                list = new ArrayList<>();
            }
        }
    }
}

public class Solution {
    /*
    * 解法一：每次将list保存到结果list的0下标的位置
    */
    public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        ArrayList<ArrayList<Integer>> wrapList = new ArrayList<ArrayList<Integer>>();
        
        if(root == null) return wrapList;
        
        queue.offer(root);
        while(!queue.isEmpty()){
            int levelNum = queue.size();
            ArrayList<Integer> subList = new ArrayList<Integer>();
            for(int i=0; i<levelNum; i++) {
                if(queue.peek().left != null) queue.offer(queue.peek().left);
                if(queue.peek().right != null) queue.offer(queue.peek().right);
                subList.add(queue.poll().val);
            }
            //每次将结果保存到下标为0的位置
            wrapList.add(0, subList);
        }
        return wrapList;
    }
    /*
	 * 解法二：
	 * 思路：用递归实现层序遍历 与正常遍历不同的是，
	 * 先进行下一层递归，再把当前层的结果保存到res中 结合代码更好理解
	 */
	List<List<Integer>> res = null;

	public List<List<Integer>> levelOrderBottom(TreeNode root) {
		res = new ArrayList<List<Integer>>();
		if (root == null)
			return res;
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.offer(root);
		levelOrderBottom(queue);

		return res;
	}

	private void levelOrderBottom(Queue<TreeNode> queue) {
		if (queue.isEmpty())
			return;
		int size = queue.size();
		ArrayList<Integer> list = new ArrayList<Integer>();
		for (int i = 0; i < size; i++) {
			TreeNode node = queue.poll();
			if (node.left != null)
				queue.offer(node.left);
			if (node.right != null)
				queue.offer(node.right);
			list.add(node.val);
		}
		// 理解堆栈的原理，先进行递归，再将list保存到res中
		levelOrderBottom(queue);
		res.add(list);
	}
}

import java.util.*;
public class Solution {
   public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
		ArrayList<ArrayList<Integer>> res = new ArrayList<>();
		if(root == null) return res;
		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(root);
		while ( ! queue.isEmpty()) {
			ArrayList<Integer> list = new ArrayList<>();
			int size = queue.size();
			for (int i = 0; i < size; i ++ ) {
				TreeNode temp = queue.poll();
				list.add(temp.val);
				if(temp.left != null) queue.add(temp.left);
				if(temp.right != null) queue.add(temp.right);
			}
			res.add(0,list);
		}
		return res;
	}
}

// 这个题参见leetcode两种解法:BFS和DFS
class Solution {
public:
    // BFS
    vector<vector<int> > levelOrderBottom(TreeNode *root)
    {
        vector<vector<int>> res;
        if(root==nullptr)
            return res;
        queue<TreeNode *> q;
        q.push(root);
        while(q.size()>0)
        {
            vector<int> level;
            for(int i=0,n=q.size();i<n;i++)
            {
                TreeNode *temp = q.front();
                q.pop();
                level.push_back(temp->val);
                if(temp->left) q.push(temp->left);
                if(temp->right) q.push(temp->right);
            }
            res.push_back(level);
        }
        reverse(res.begin(),res.end());
        return res;
    }
};

 // DFS
     int getHeight(TreeNode *root)
     {
        if(!root) return 0;
        return max(getHeight(root->left),getHeight(root->right))+1;
     }
     vector<vector<int> > levelOrderBottom(TreeNode *root)
     {      
         if(!root) return vector<vector<int>>();
         vector<vector<int>> res(getHeight(root),vector<int>());
         dfs(root,res.size()-1,res);
         return res;         
     }
     void dfs(TreeNode *root,int height,vector<vector<int>> &res)
     {
        if(!root)
            return;
        res[height].push_back(root->val);
        dfs(root->left,height-1,res);
        dfs(root->right,height-1,res);
     }    

典型的用队列做宽度优先搜索 最后reverse一下即可

class Solution {
public:
    vector<vector<int> > levelOrderBottom(TreeNode *root) {
        vector<vector<int> > res;
        if(!root) return res;
        queue<TreeNode* > qu; qu.push(root);
        while(!qu.empty()){
            int size = qu.size();
            vector<int> tmp;
            for(int i = 0; i < size; i++){
                TreeNode *head = qu.front(); qu.pop();
                tmp.push_back(head->val);
                if(head->left) qu.push(head->left);
                if(head->right) qu.push(head->right);
            }
            res.push_back(tmp);
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

class Solution {
public:
    vector<vector<int> > levelOrderBottom(TreeNode *root) {
        queue<TreeNode*> q;
        vector<vector<int>> vv;
        if (root == NULL){
            return vv;
        }
        int before = 0;
        int current = 0;
        if (root != NULL && q.empty()){
            q.push(root);
            current++;
        }
        while (!q.empty()){
            vector<int>v;
            before = current;
            current = 0;
            while(before--){
                TreeNode *t = q.front();
                if (t->left != NULL){
                    q.push(t->left);
                    current++;
                }
                if (t->right != NULL){
                    q.push(t->right);
                    current++;
                }
                v.push_back(t->val);
                q.pop();
            }
            vv.push_back(v);
        }
        vector<vector<int>> res;
        for (int i = vv.size()-1; i >= 0; --i){
            res.push_back(vv[i]);
        }
        return res;
    }
};

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > levelOrderBottom(TreeNode* root) {
        // write code here
        // 时间复杂度O(N)，空间复杂度O(logN)
        vector<vector<int>> res;
        stack<vector<int>> stk;
        if (root == nullptr) return res;
        queue<TreeNode*> que;
        que.emplace(root);
        int size;
        while (!que.empty()) {
            size = que.size();
            vector<int> level;
            while (size--) {
                root = que.front();
                que.pop();
                level.emplace_back(root->val);
                if (root->left) que.emplace(root->left);
                if (root->right) que.emplace(root->right);
            }
            stk.emplace(level);
        }
        while (!stk.empty()) {
            res.emplace_back(stk.top());
            stk.pop();
        }
        return res;
    }
};

public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if(root == null) return result;
        ArrayList<TreeNode> queue = new ArrayList<TreeNode>();
        queue.add(root);
        while(queue.size() != 0){
            ArrayList<Integer> arr = new ArrayList<Integer>();
            int size = queue.size();
            for(int i = 0; i < size; i++){
                TreeNode node = queue.get(0);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
                arr.add(node.val);
                queue.remove(0);
            }
            result.add(0, arr);
        }
        return result;
    }
}

public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
        if(root==null) return new ArrayList<>();
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.add(root);q.add(null);
        bfs(result,q);
        Collections.reverse(result);
        return result;
    }
    
    public void bfs(ArrayList<ArrayList<Integer>> result,Queue<TreeNode> q) {
        ArrayList<Integer> temp =new ArrayList<Integer> ();
        TreeNode t = q.poll();
        while(t!=null) {
            temp.add(t.val);
            if(t.left!=null) q.add(t.left);
            if(t.right!=null) q.add(t.right);
            t=q.poll();
        }
        result.add(temp);
        if(q.size()!=0){
            q.add(null);
            bfs(result,q);
        }
    }
}

class Solution {
public:
    vector<vector<int> > levelOrderBottom(TreeNode *root) {
        vector<vector<int>> vec;
        if(root==nullptr) return vec;
        queue<TreeNode *> tree_queue;
        tree_queue.push(root);
        while(!tree_queue.empty())
        {
            vector<int> small_vec;
            int count = tree_queue.size();
            while(count--)
            {
                TreeNode * get_one = tree_queue.front();
                tree_queue.pop();
                small_vec.push_back(get_one->val);
                if(get_one->left)
                    tree_queue.push(get_one->left);
                if(get_one->right)
                    tree_queue.push(get_one->right);
                
            }
            vec.push_back(small_vec);
        }
        reverse(vec.begin(),vec.end());
        return vec;
    }
};

/*思路：利用树的层次遍历，通过获取队列的大小设置一个循环，即可保证队列里全是同一层的树节点，然后遍历这些节点
，依次添加到list中，最后利用Collections自带的reverse方法对ArrayList进行反转***作即可*/
import java.util.*;
public class Solution {
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
        if(root==null)
            return res;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            ArrayList<Integer> list=new ArrayList<>();
            //获取队列大小
            int size=queue.size();
            for(int i=0;i<size;i++){
                TreeNode node=(TreeNode)queue.poll();
                if(node.left!=null){
                   queue.offer(node.left);
                }
                if(node.right!=null){
                   queue.offer(node.right);
                 }
                 list.add(node.val);
            }
            res.add(new ArrayList<>(list));
        }
        //对res进行反转***作
        Collections.reverse(res);
        return res;
    }
}

vector<vector<int> > levelOrder(TreeNode *root) {
        vector<vector<int> > res;
        if(root == nullptr) return res;
        queue<TreeNode*> cur, next; // cur:保存当前层的节点, next:保存下一层的节点
        vector<int> level;  // 保存每一层的数据

        cur.push(root);
        while(!cur.empty()) {
            while(!cur.empty()) {
                TreeNode* node = cur.front();
                cur.pop();
                level.push_back(node->val);
                if(node->left) next.push(node->left);
                if(node->right) next.push(node->right);
            }
            res.push_back(level);
            level.clear();
            // 访问下一层节点
            swap(next, cur);
        }
        // levelOrderBottom
        // reverse(res.begin(), res.end());
        return res;
    }

 vector<vector<int> > levelOrderBottom(TreeNode *root) {
        vector<vector<int>> res;
        if(!root)
            return res;
        vector<int> tmp;
        deque<TreeNode *> que;
        que.push_back(root);
        TreeNode *last=root;
        TreeNode *nlast=NULL;
        while(!que.empty()){
            TreeNode *p=que.front();
            que.pop_front();
            tmp.push_back(p->val);
            if(p->left){
                que.push_back(p->left);
                nlast=p->left;
            }
            if(p->right){
                que.push_back(p->right);
                nlast=p->right;
            }
            if(last==p){
                res.push_back(tmp);
                tmp.clear();
                last=nlast;
            }
        }
        reverse(res.begin(),res.end());
        return res;
    }

C++ solution

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode *root) {

        vector<vector<int>> result;
        if (root == NULL) { return result; }
        vector<TreeNode *> nodeStack;

        nodeStack.push_back(root);
        while (nodeStack.size()) {
            vector<int> value;
            vector<TreeNode *> nextLevel;
            for (int i = 0; i < nodeStack.size(); i++) {
                value.push_back(nodeStack[i]->val);
            }
            for (int i = 0; i < nodeStack.size(); i++) {
                if (nodeStack[i]->left) {
                    nextLevel.push_back(nodeStack[i]->left);
                }
                if (nodeStack[i]->right) {
                    nextLevel.push_back(nodeStack[i]->right);
                }
            }
            nodeStack = nextLevel;

            result.push_back(value);
        }
        reverse(result.begin(),result.end());
        return result;


    }
};

class Solution {
public:
    vector<vector<int> > levelOrderBottom(TreeNode *root) {
        vector<vector<int> > result;
        if(root == NULL)
        	return result;
        
        queue<TreeNode *> q;
        q.push(root);
        
        while(!q.empty())
        {
        	vector<int> level;
        	int n = q.size();
        	for(int i=0;i<n;i++)
        	{
        		TreeNode *cur = q.front();
        		q.pop();
				level.push_back(cur->val);
				if(cur->left != NULL)
					q.push(cur->left);
				if(cur->right != NULL)
					q.push(cur->right);
			}
			result.push_back(level);
		}
		reverse(result.begin(),result.end());	//自底向上倒序 
    	return result; 
	}
};

//层序遍历
 vector<vector<int> > levelOrderBottom(TreeNode *root) {
        vector<vector<int>> result;
        if(root==NULL)
            return result;
     	TreeNode *tail=root,*temp,*last=root;
       	queue<TreeNode *> que;
	vector<int> arr;
	stack<vector<int>> stk;
       	que.push(root);
       	while(!que.empty()){
	    temp=que.front();
            arr.push_back(temp->val);
	    que.pop();
	    if(temp->left!=NULL){
		que.push(temp->left);
		last=temp->left;
	    }
	    if(temp->right!=NULL){
		que.push(temp->right);
		last=temp->right;
	    }
	    if(temp == tail){
                tail=last;
		stk.push(arr);
		arr.clear();
	    }
	}
	while (!stk.empty())
	{
		result.push_back(stk.top());
		stk.pop();
	}
	return result;
   }