题目107. Binary Tree Level Order Traversal II

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,null,null,15,7],
3
/
9 20
/
15 7
return its bottom-up level order traversal as:
[
[15,7],
[9,20],
[3]
]

1,递归的写法

思路:本质还是二叉树的层次遍历

public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new LinkedList<List<Integer>>();
        if(root == null){
            return result;
        }
    
        List<TreeNode> curLevelNodes = new ArrayList<TreeNode>();
        curLevelNodes.add(root);
        bfs(curLevelNodes,result);
        return result;
     }
     private void bfs(List<TreeNode> curLevelNodes,List<List<Integer>> result){
        if(!curLevelNodes.isEmpty()){
        List<Integer> levelResult = new ArrayList<Integer>();
        List<TreeNode> nextLevelNodes = new ArrayList<TreeNode>();
        for(TreeNode node : curLevelNodes){
            levelResult.add(node.val);
            if(node.left != null){
                nextLevelNodes.add(node.left);
            }
            if(node.right != null){
                nextLevelNodes.add(node.right);
            }
        }
        result.add(0,levelResult);
        bfs(nextLevelNodes,result);   
        }
     }

2,非递归

public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new LinkedList<List<Integer>>();
        if(root == null){
            return result;
        }
        List<TreeNode> curLevelNodes = new ArrayList<TreeNode>();
        curLevelNodes.add(root);
        while(!curLevelNodes.isEmpty()){
            List<Integer> levelResult = new ArrayList<Integer>();
            List<TreeNode> nextLevelNodes = new ArrayList<TreeNode>();
            for(TreeNode node : curLevelNodes){
                levelResult.add(node.val);
                if(node.left != null){
                    nextLevelNodes.add(node.left);
                }
                if(node.right != null){
                    nextLevelNodes.add(node.right);
                }
            }
            curLevelNodes = nextLevelNodes;
            result.add(0,levelResult);
        }
        return result;
    }