題目截圖
depth and height are properties of a node:
The depth of a node is the number of edges from the node to the tree's root node.
A root node will have a depth of 0.The height of a node is the number of edges on the longest path from the node to a leaf.
A leaf node will have a height of 0.
Properties of a tree:
The height of a tree would be the height of its root node,
or equivalently, the depth of its deepest node.Note that depth doesn't make sense for a tree.
題解很巧妙的使用了 height. 與 Convert Sorted List to Binary Search Tree 有異曲同工之妙埋同。
Find Leaves of Binary Tree 題解
public List<List<Integer>> findLeaves(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
dfsHeight(root, res);
return res;
}
private int dfsHeight(TreeNode root, List<List<Integer>> res) {
if (root == null) {
return -1;
}
int leftChildDepth = dfsHeight(root.left, res);
int rightChildDepth = dfsHeight(root.right, res);
int depth = Math.max(leftChildDepth, rightChildDepth) + 1;
if (res.size() <= depth) {
ArrayList<Integer> list = new ArrayList<>();
res.add(list);
}
res.get(depth).add(root.val);
return depth;
}
Convert Sorted List to Binary Search Tree 題解
class Solution {
ListNode currentListNode = null;
public TreeNode sortedListToBST(ListNode head) {
int size = getListLength(head);
currentListNode = head;
return inorderGenerator(size);
}
private TreeNode inorderGenerator(int len) {
if (len == 0) {
return null;
}
int half = len / 2;
TreeNode leftChild = inorderGenerator(half);
TreeNode root = new TreeNode(currentListNode.val);
currentListNode = currentListNode.next;
TreeNode rightChild = inorderGenerator(len - half -1); //這里的減1喳张，是因?yàn)?root 已經(jīng)占了一個(gè) Node
root.left = leftChild;
root.right = rightChild;
return root;
}
private int getListLength(ListNode head) {
int size = 0;
ListNode runner = head;
while (runner != null) {
size++;
runner = runner.next;
}
return size;
}
}
