chenxin's blog
0%

算法题-二叉树

发表于 更新于 分类于 
1
2
3
4
5
6
7
8
9
10
11
12
13
//二叉树结点定义
 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;
     }
 }

二叉树的遍历

前序非递归：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public ArrayList<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> arr = new ArrayList<Integer>();
        if (root == null) return arr;
        LinkedList<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            arr.add(node.val);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return arr;
    }

中序非递归，把所有的左结点入栈，再挨个弹出来：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public ArrayList<Integer> inorderTraversal(TreeNode root) {
       ArrayList<Integer> arr = new ArrayList<Integer>();
       if (root == null) return arr;
       LinkedList<TreeNode> stack = new LinkedList<>();
       TreeNode node = root;
       while (!stack.isEmpty() || node != null) {
           if (node != null) {
               stack.push(node);
               node = node.left;
           } else {
               node = stack.pop();
               arr.add(node.val);
               node = node.right;
           }
       }
       return arr;
   }

230. 二叉搜索树中第K小的元素

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
示例 1:

输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 1
示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
输出: 3

思路：中序遍历，top k的k只能已成员变量的形式计数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int kthSmallest(TreeNode root, int k) {
        mK = k;
        val = 0;
        inOrder(root);
        return val;
}

private int val;
private int mK = 0;

void inOrder(TreeNode node){
    if(node == null) {
        return;
    }
    inOrder(node.left);
    if(--mK == 0){
        val =  node.val;
        return;
    }
    inOrder(node.right);

}

98. 验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

思路：二叉搜索树的特点是每个结点都在一个区间内，利用这个区间判断，root在Int.MAX到Int.MIN区间，其余结点类推

1
2
3
4
5
6
7
8
public boolean isValidBST(TreeNode root) {
    return isBST(root,Integer.MIN_VALUE,Integer.MAX_VALUE);
}

private boolean isBST(TreeNode root, int lo, int hi) {
    if (root == null) return true;
    return root.val > lo && root.val < hi && isBST(root.left, lo, root.val) && isBST(root.right, root.val, hi);
}

103. 二叉树的锯齿形层序遍历

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

思路：交替使用两个栈，第一个栈保存从左向右的，第二栈保存从右向左的结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
       Stack<TreeNode> s1 = new Stack<>();
       Stack<TreeNode> s2 = new Stack<>();
       ArrayList<ArrayList<Integer>> arr = new ArrayList<>();
       if (root == null) return arr;
       ArrayList<Integer> list = new ArrayList<>();
       s1.add(root);
       while (!s1.isEmpty() || !s2.isEmpty()) {
           while (!s1.isEmpty()) {
               TreeNode node = s1.pop();
               list.add(node.val);
               if (node.left != null) {
                   s2.add(node.left);
               }
               if (node.right != null) {
                   s2.add(node.right);
               }
           }
           if (!list.isEmpty()) {
               arr.add(list);
               list = new ArrayList<>();
           }
           while (!s2.isEmpty()) {
               TreeNode node = s2.pop();
               list.add(node.val);
               if (node.right != null) {
                   s1.add(node.right);
               }
               if (node.left != null) {
                   s1.add(node.left);
               }
           }
           if (!list.isEmpty()) {
               arr.add(list);
               list = new ArrayList<>();
           }
       }
       return arr;
   }

109. 有序链表转换二叉搜索树

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

1
2
3
4
5
6
7
8
9
10
11
12
示例:

给定的有序链表： [-10, -3, 0, 5, 9],

一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

思路：找到链表中间结点，然后构建treenode 结点，依次遍历左边链表、右边链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public TreeNode sortedListToBST(ListNode head) {
        return sortedListToBST(head,null);
   }
public TreeNode sortedListToBST(ListNode start,ListNode end) {
        if(start == end) return null;
        ListNode middle = middleNode(start,end);
        TreeNode root = new TreeNode(middle.val);
        root.left = sortedListToBST(start,middle);
        root.right = sortedListToBST(middle.next,end);
        return root;
}

ListNode middleNode(ListNode start,ListNode end){
    ListNode fast = start,slow = start;

    while(fast != end && fast.next != end ){
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
}

//第二种方法，直接使用数组得了。。
public TreeNode sortedListToBST(ListNode head) {
      ArrayList<Integer> list = new ArrayList<>();
      while (head != null) {
          list.add(head.val);
          head = head.next;
      }
      return generate(list, 0, list.size() - 1);
  }

  private TreeNode generate(List<Integer> list, int lo, int hi) {
      if (lo > hi) return null;
      int mid = (lo + hi+1) / 2;
      TreeNode r = new TreeNode(list.get(mid));
      r.left = generate(list, lo, mid - 1);
      r.right = generate(list, mid + 1, hi);
      return r;
  }

102. 二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
思路：广度优先遍历，使用队列模拟这个过程：
访问一个结点时把它的子结点加入队列，并用一个tail指针指向最后入队的那个结点，它代表下一排的最后一个，如果正在访问的结点当前行的最后一个，那就代表要换行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        ArrayList<ArrayList<Integer>> arr = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> arr2 = new ArrayList<Integer>();
        if(root == null) return arr;
        TreeNode last = root, nlast = root;
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            arr2.add(node.val);
//            System.out.print(node.val+" ");
            if(node.left != null) {
                nlast = node.left;
                queue.offer(node.left);
            }
            if(node.right != null){
                nlast = node.right;
                queue.offer(node.right);
            }
            if(node == last) {
                last = nlast;
                arr.add(arr2);
                arr2 = new ArrayList<Integer>();
            }

        }
        return arr;

    }

108. 将有序数组转换为二叉搜索树

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

**思路：
二叉搜索树：
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

二叉平衡搜索树（AVL）：
左子树与右子树高度之差的绝对值不超过1

[1,2]数组：mid = (lo + hi+1) / 2 这样取出来就是两个中间大的那个作为父结点。mid = (lo + hi) / 2 取的小的那个
**

1
2
3
4
5
6
7
8
9
10
11
12
13
public TreeNode sortedArrayToBST(int[] num) {
        if (num == null || num.length == 0) return null;
        return gen(num, 0, num.length - 1);
    }

    private TreeNode gen(int[] num, int lo, int hi) {
        if (lo > hi) return null;
        int mid = (lo + hi+1) / 2;
        TreeNode node = new TreeNode(num[mid]);
        node.left = gen(num, lo, mid - 1);
        node.right = gen(num, mid + 1, hi);
        return node;
    }

112. 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。
思路：从上向下分摊sum，只要有一个子结点的值等于最后剩余的值都ok

1
2
3
4
5
6
7
public boolean hasPathSum(TreeNode root, int sum) {
     if (root == null) return false;
     if (root.right == null && root.left == null) {
         return sum - root.val == 0;
     }
     return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
 }

113. 路径总和 II

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

思路：深度优先遍历，add与remove成对，记得remove的参数是index

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {

       if (root == null) {
           return new ArrayList<>();
       }
       ArrayList<ArrayList<Integer>> arrs = new ArrayList<>();
       ArrayList<Integer> arr = new ArrayList<>();
       pathSumIn(arrs, arr, root, sum);
       return arrs;
   }

   public void pathSumIn(ArrayList<ArrayList<Integer>> arrs, ArrayList<Integer> arr, TreeNode root, int sum) {
       if (root.left == null && root.right == null) {
           int v = sum - root.val;
           if (v == 0) {
               arr.add(root.val);
               arrs.add((ArrayList<Integer>) arr.clone());
               arr.remove(arr.size() - 1);
           }
           return;
       }
       arr.add(root.val);
       if (root.left != null) {
           pathSumIn(arrs, arr, root.left, sum - root.val);
       }
       if (root.right != null) {
           pathSumIn(arrs, arr, root.right, sum - root.val);
       }
       arr.remove(arr.size() - 1);
   }

104. 二叉树的最大深度

给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

1
2
3
4
5
6
public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    int left = maxDepth(root.left);
    int right = maxDepth(root.right);
    return left > right ? left + 1 : right + 1;
}

111. 二叉树的最小深度

给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

思路：求左右子树的最小高度，最后加1即可，但当发现结点的左子树或右子树的高度为0时要排除它，因为此时就证明这个结点一定不是一个叶子结点

1
2
3
4
5
6
7
8
9
10
11
12
13
public int run(TreeNode root) {
    if (root == null) return 0;
    int left = run(root.left);
    int right = run(root.right);
    //某个子树的高度为0时，直接计算另外的一个子树
    if (left == 0) {
        return right + 1;
    } else if (right == 0) {
        return left + 1;
    }
    //子树的高度都不会为0时，选最小的那个子树
    return left > right ? right + 1 : left + 1;
}

538. 把二叉搜索树转换为累加树

给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

1
2
3
4
5
6
7
8
9
Input: The root of a Binary Search Tree like this:
              5
            /   \
           2     13

Output: The root of a Greater Tree like this:
             18
            /   \
          20     13

思路：从右子树开始的中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private static void order(TreeNode root, int[] s) {
 if (root == null) return;
 order(root.right, s);
 root.val += s[0];
 s[0] = root.val;
//        System.out.print(s[0]+" ");
 order(root.left, s);
}

public TreeNode convertBST(TreeNode root) {
 int[] s = {0};
 order(root, s);
 return root;
}

129. 求根节点到叶节点数字之和

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字：

1
2
3
4
5
6
7
8
    1
  /   \
 2     3

The root-to-leaf path1->2represents the number12.
The root-to-leaf path1->3represents the number13.

Return the sum = 12 + 13 =25.

思路：深度优先遍历，前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int sumNumbers(TreeNode root) {
    return dfs(root, 0);
}

public int dfs(TreeNode root, int prevSum) {
    if (root == null) {
        return 0;
    }
    int sum = prevSum * 10 + root.val;
    if (root.left == null && root.right == null) {
        return sum;
    } else {
        return dfs(root.left, sum) + dfs(root.right, sum);
    }
}

96. 不同的二叉搜索树

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
思路：动态规划，0个结点1种、1个结点1种、2个结点等于左边的情况乘以右边的情况，要记住第n个结点，不能把n算进来，n-1的元素中两两组合

1
2
3
4
5
6
7
8
9
10
11
public int numTrees(int n) {
     int[] result = new int[n + 1];
     result[0] = 1;
     result[1] = 1;
     for (int i = 2; i < result.length; i++) {
         for (int j = 0; j < i; j++) {
             result[i] += result[j] * result[i - j-1];
         }
     }
     return result[n];
 }

116. 填充每个节点的下一个右侧节点指针

给定一个 完全二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。

1
2
3
4
5
6
struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

思路：前序遍历，再次回到遍历的这个结点时它的next已经设置了，所以可以直接访问到next指针，方便设置right的next

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public void connect(Node parent,Node root,boolean isRight) {
       if(root == null) return;
       if(parent != null){
           if(!isRight){//左结点直接设置
               root.next = parent.right;
           }else {//右结点需要利用next指针
               Node next = parent;
               next = next.next;
               if(next != null){
                   root.next = next.left;
               }
           }
       }
       connect(root,root.left,false);
       connect(root,root.right,true);
   }

    public Node connect(Node root) {
           connect(null,root,false);
           return root;
   }

117. 填充每个节点的下一个右侧节点指针 II

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。

思路：广度优先遍历，与填完整二叉树不同的是，我们不能用递归的方式完成广度优先遍历，必须使用队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public Node connect(Node root) {
       if(root == null) return null;
       Queue<Node> queue = new LinkedList<Node>();

       Node tail = root;
       Node nextTail = root;
       Node preNode = null;
       queue.offer(root);

       while(!queue.isEmpty()){
           Node curNode = queue.remove();
           if(curNode.left != null){
               queue.offer(curNode.left);
               nextTail = curNode.left;
           }
           if(curNode.right != null){
               queue.offer(curNode.right);
               nextTail = curNode.right;
           }
           if(preNode != null){
               preNode.next = curNode;
           }
           preNode = curNode;
           if(curNode == tail){
               tail = nextTail;
               nextTail = null;
               preNode = null;
           }

       }
       return root;
   }

114. 二叉树展开为链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
For example, given the following tree:

    1
   / \
  2   5
 / \   \
3   4   6
The flattened tree should look like:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

**思路，后序遍历，遍历到一个root结点时，只有它存在左子结点才处理：
1、遍历找到左子结点的最右结点
2、该最右结点指向root结点的右结点
3、再把左子结点插入到右结点中
**

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void flatten(TreeNode root) {
      if (root == null) return;
      flatten(root.left);
      flatten(root.right);
      if (root.left != null) {
          TreeNode tail = root.left;
          while (tail.right != null) {
              tail = tail.right;
          }
          TreeNode temp = root.right;
          root.right = root.left;
          tail.right = temp;
          root.left = null;
      }

  }

110. 平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

思路：求出每个结点的左右子树的最大高度，然后比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static private int maxDepth(TreeNode root) {
       if (root == null) return 0;
       if (root.left == null && root.right == null) return 1;
       int left = maxDepth(root.left);
       int right = maxDepth(root.right);
       return left > right ? left + 1 : right + 1;
   }

   public boolean isBalanced(TreeNode root) {
       if (root == null) return true;
       int left = maxDepth(root.left);
       int right = maxDepth(root.right);
       if (Math.abs(left - right) > 1) return false;
       return isBalanced(root.left) && isBalanced(root.right);
   }

100. 相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

1
2
3
4
5
6
public boolean isSameTree(TreeNode p, TreeNode q) {
    if(q == null && p == null) return true;
    if(q== null || p == null) return false;
    if(q.val== p.val) return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    return false;
}

101. 对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

1
2
3
4
5
6
7
8
9
10
11
public boolean isSymmetric(TreeNode root) {
    if (root == null) return true;
    return isSame(root.right, root.left);
}

private boolean isSame(TreeNode p, TreeNode q) {
    if (p == null && q == null) return true;
    if (p == null || q == null) return false;
    if (p.val == q.val) return isSame(p.left, q.right) && isSame(p.right, q.left);
    return false;
}

非递归,用一个栈就行：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public boolean isSymmetric(TreeNode root) {
    if (root == null) return true;
    return isSame2(root.right, root.left);
}

public boolean isSame2(TreeNode p, TreeNode q) {
    if (p == null && q == null) return true;
    if (p == null || q == null) return false;
    LinkedList<TreeNode> stack = new LinkedList<>();
    stack.push(p);
    stack.push(q);
    while (!stack.isEmpty()) {
        TreeNode n1 = stack.pop();
        TreeNode n2 = stack.pop();
        if (n1.val != n2.val) return false;
        if (n1.left != null && n2.right != null) {
            stack.push(n1.left);
            stack.push(n2.right);
        } else if (n1.left != null || n2.right != null) {
            return false;
        }

        if (n1.right != null && n2.left != null) {
            stack.push(n1.right);
            stack.push(n2.left);
        } else if (n1.right != null || n2.left != null) {
            return false;
        }
    }
    return true;
}

99. 恢复二叉搜索树

给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。

思路：中序遍历得到升序数组，然后找到其中的逆序的两个结点的位置，找到第一对逆序结点时取第一个结点的位置，第二对逆序结点取第二个结点的位置，如果没有第二对逆序结点，那说明是相邻的两个结点被交换了。最后再次执行遍历二叉树，对两个结点重新赋值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public void recoverTree(TreeNode root) {
      List<Integer> nodes = new LinkedList();
      inOrder(root,nodes);
      List<Integer> two = findTowNode(nodes);
      if(two.size() > 1){
           recover(root,nodes.get(two.get(0)),nodes.get(two.get(1)));
      }else {
          recover(root,nodes.get(two.get(0)),nodes.get(two.get(0)+1));
      }
  }

  void recover(TreeNode root,int x,int y){
      if(root == null) return;
      if(root.val == x){
          root.val = y;
      }else if(root.val == y){
          root.val = x;
      }
      recover(root.left,x,y);
      recover(root.right,x,y);
  }

  List<Integer> findTowNode(List<Integer> nodes){
      List<Integer> two = new ArrayList();
      boolean isAddOne = false;
      for(int i=0;i< nodes.size()-1;i++){
          if(nodes.get(i) > nodes.get(i+1)){
              if(!isAddOne){
                  isAddOne = true;
                   two.add(i);
              } else {
                  two.add(i+1);
              }
          }
      }
      return two;
  }

  void inOrder(TreeNode root,List<Integer> nodes){
      if(root == null) return;
      inOrder(root.left,nodes);
      nodes.add(root.val);
      inOrder(root.right,nodes);
  }

方法二：中序遍历，同时保存结点和与之对应的值到两个list，对保存值数组排序，然后再依次重新赋值给保存结点的List，完事。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void recoverTree(TreeNode root) {
       inOrder(root);
       Collections.sort(vals);
       for (int i = 0; i < vals.size(); i++) {
           nodes.get(i).val = vals.get(i);
       }
   }

   LinkedList<TreeNode> nodes = new LinkedList<>();
   ArrayList<Integer> vals = new ArrayList<>();

   private void inOrder(TreeNode root) {
       if (root == null) return;
       inOrder(root.left);
       nodes.add(root);
       vals.add(root.val);
       inOrder(root.right);
   }

107. 二叉树的层序遍历 II

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

思路：得到的每行添加到返回的List的第一个就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public List<List<Integer>> levelOrderBottom(TreeNode root) {

        List<List<Integer>> arrs = new ArrayList<>();
        if (root == null) return arrs;
        ArrayList<Integer> arr = new ArrayList<>();
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        TreeNode tail = root;
        TreeNode nextTail = root;
        while (!queue.isEmpty()) {
            TreeNode node = queue.remove();

            if (node.left != null) {
                queue.offer(node.left);
                nextTail = node.left;
            }
            if (node.right != null) {
                queue.offer(node.right);
                nextTail = node.right;
            }
            arr.add(node.val);
            if (node == tail) {
                arrs.add(0,arr);
                arr = new ArrayList<>();
                tail = nextTail;
            }
        }
        return arrs;
    }