Leetcode 107) Binary Tree Level Order Traversal II

22 Jul 2021 in Algorithms

내 답안

/**
 * 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>> levelOrderBottom(TreeNode root) {
        Stack<List<TreeNode>> s = new Stack<>();
        List<TreeNode> g = new ArrayList<>();
        List<List<Integer>> res = new ArrayList<List<Integer>>();

        if(root==null){
            return res;
        }

        g.add(root);
        s.add(g);
        boolean end =true;

        while(true){
            end=true;
            g = new ArrayList<>();
            for(TreeNode tn : s.peek()){
                if(tn.left!=null){
                    end=false;
                    g.add(tn.left);
                }
                if(tn.right!=null){
                    end=false;
                    g.add(tn.right);
                }
            }
            if(end){
                break;
            }
            s.add(g);
        }
        while(!s.isEmpty()){
            List<TreeNode> tmp =s.pop();
            List<Integer> tmp2= new ArrayList<>();
            for(TreeNode i : tmp){
                tmp2.add(i.val);
            }
            res.add(tmp2);
        }
        return res;


    }
}

다른 답안

/**
 * 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<List<Integer>> ans = new ArrayList<>();
    public void dfs(TreeNode root, int level, List<List<Integer>> ans)
    {
        if(root == null)
        {
            return;
        }

        if(level >= ans.size())
        {
            ans.add(0,new ArrayList<Integer>());
        }
        dfs(root.left,level+1,ans);
        dfs(root.right,level+1,ans);
        ans.get(ans.size()-level-1).add(root.val);


    }
    public List<List<Integer>> levelOrderBottom(TreeNode root) {

        if(root == null)
        {
            return ans;
        }

        dfs(root, 0,ans);
        return ans;

    }
}