填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。
初始状态下，所有 next 指针都被设置为 NULL 。
解法：层次遍历
class Solution {
public Node connect(Node root) {
if (root == null) {
return null;
}
Queue<Node> queue = new ArrayDeque<Node>();
queue.offer(root);
while (!queue.isEmpty()) {
int n = queue.size();
Node last = null;
for (int i = 1; i <= n; ++i) {
Node f = queue.poll();
if (f.left != null) {
queue.offer(f.left);
}
if (f.right != null) {
queue.offer(f.right);
}
if (i != 1) {
last.next = f;
}
//last是本层的第一个节点
last = f;
}
}
return root;
}
}
给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
解法一，前序遍历
//递归法
class Solution {
public void flatten(TreeNode root) {
List<TreeNode> list = new ArrayList<TreeNode>();
preorderTraversal(root, list);
int size = list.size();
for (int i = 1; i < size; i++) {
TreeNode prev = list.get(i - 1), curr = list.get(i);
prev.left = null;
prev.right = curr;
}
}
public void preorderTraversal(TreeNode root, List<TreeNode> list) {
if (root != null) {
list.add(root);
preorderTraversal(root.left, list);
preorderTraversal(root.right, list);
}
}
}
迭代法
class Solution {
public void flatten(TreeNode root) {
List<TreeNode> list = new ArrayList<TreeNode>();
Deque<TreeNode> stack = new LinkedList<TreeNode>();
TreeNode node = root;
while (node != null || !stack.isEmpty()) {
while (node != null) {
list.add(node);
stack.push(node);
node = node.left;
}
node = stack.pop();
node = node.right;
}
int size = list.size();
for (int i = 1; i < size; i++) {
TreeNode prev = list.get(i - 1), curr = list.get(i);
prev.left = null;
prev.right = curr;
}
}
}
解法2：
将左子树插入到右子树的地方
将原来的右子树接到左子树的最右边节点
考虑新的右子树的根节点，一直重复上边的过程，直到新的右子树为 null
public void flatten(TreeNode root) {
while (root != null) {
//左子树为 null，直接考虑下一个节点
if (root.left == null) {
root = root.right;
} else {
// 找左子树最右边的节点
TreeNode pre = root.left;
while (pre.right != null) {
pre = pre.right;
}
//将原来的右子树接到左子树的最右边节点
pre.right = root.right;
// 将左子树插入到右子树的地方
root.right = root.left;
root.left = null;
// 考虑下一个节点
root = root.right;
}
}
}
class Solution {
int maxSum =Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxGain(root);
return maxSum;
}
private int maxGain(TreeNode root){
if(root ==null){
return 0;
}
int leftGain = Math.max(maxGain(root.left),0);
int rightGain=Math.max(maxGain(root.right),0);
int newPath = root.val+leftGain+rightGain;
maxSum=Math.max(maxSum, newPath);
return root.val+Math.max(leftGain,rightGain);
}
}
class BSTIterator {
private TreeNode cur;
private Deque<TreeNode> stack;
public BSTIterator(TreeNode root) {
cur = root;
stack = new LinkedList<TreeNode>();
}
public int next() {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
int ret = cur.val;
cur = cur.right;
return ret;
}
public boolean hasNext() {
return cur != null || !stack.isEmpty();
}
}
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
解法一，最简单方法递归。但是没有利用到完全二叉树的特定。
class Solution {
public int countNodes(TreeNode root) {
if(root == null) {
return 0;
}
int left = countNodes(root.left);
int right = countNodes(root.right);
return left+right+1;
}
}
解法二，通过对于最大层数为 h 的完全二叉树，节点个数一定在 2^h,2^{h+1}-1 的范围内，可以在该范围内通过二分查找的方式得到完全二叉树的节点个数。
先找出level，然后通过二分查找法查看对应的节点是否存在。
如果第 k 个节点位于第 h 层，则 k 的二进制表示包含 h+1 位，其中最高位是 1，其余各位从高到低表示从根节点到第 k 个节点的路径，0 表示移动到左子节点，1 表示移动到右子节点。通过位运算得到第 k 个节点对应的路径，判断该路径对应的节点是否存在，即可判断第 k 个节点是否存在。
class Solution {
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
int level = 0;
TreeNode node = root;
while (node.left != null) {
level++;
node = node.left;
}
int low = 1 << level, high = (1 << (level + 1)) - 1;
while (low < high) {
int mid = (high - low + 1) / 2 + low;
//判断存在，所以值要=mid，然后根据low的值去设置mid的值。
if (exists(root, level, mid)) {
low = mid;
} else {
high = mid - 1;
}
}
return low;
}
public boolean exists(TreeNode root, int level, int k) {
int bits = 1 << (level - 1);
TreeNode node = root;
while (node != null && bits > 0) {
if ((bits & k) == 0) {
node = node.left;
} else {
node = node.right;
}
bits >>= 1;
}
return node != null;
}
}