最最基本的 Preorder, Inorder, Postorder Traverse
Binary Tree preorder traverse
Binary Tree inorder traverse
Binary Tree postorder traverse
Delete Node in BST;
思路：首先搜索到delete的node，然后分三种情况讨论，
1.左边空，return 右边
2.右边空，return 左边
3.左右两边都不空，找到最右边的最小值，然后把root改成最右边的最小值，然后delete那个最右边的最小node。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if(root == null) {
return null;
}
if(root.val < key) {
root.right = deleteNode(root.right, key);
} else if(root.val > key) {
root.left = deleteNode(root.left, key);
} else {
// root.val == key;
if(root.left == null) {
root = root.right;
} else if(root.right == null) {
root = root.left;
} else {
// root.left != null && root.right != null;
TreeNode leftminnode = findLeftMinNode(root.right);
root.val = leftminnode.val;
root.right = deleteNode(root.right, leftminnode.val);
}
}
return root;
}
private TreeNode findLeftMinNode(TreeNode node) {
while(node != null && node.left != null) {
node = node.left;
}
return node;
}
}
Inorder Successor in BST
思路：首先找到P点，同时记录过程中最后一个左拐的点，也就是有可能是大于p的第一个点 （如果p没有右边儿子的话）
如果p有右边儿子，那么就是右边儿子最左边的那个node，否则就是last left turn node；
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
if(root == null) {
return null;
}
TreeNode lastleft = null;
TreeNode node = root;
while(node != p) {
if(node.val < p.val) {
node = node.right;
} else if(node.val > p.val) {
lastleft = node;
node = node.left;
} else {
break; // find it;
}
}
if(p.right != null) {
return findLeftMinNode(p.right);
} else {
return lastleft;
}
}
private TreeNode findLeftMinNode(TreeNode node) {
while(node != null && node.left != null) {
node = node.left;
}
return node;
}
}
Inorder predecessor in BST
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root: the given BST
* @param p: the given node
* @return: the in-order predecessor of the given node in the BST
*/
public TreeNode inorderPredecessor(TreeNode root, TreeNode p) {
if(root == null || p == null) {
return null;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode node = root;
while(node != null) {
stack.push(node);
node = node.left;
}
TreeNode pre = null;
while(!stack.isEmpty()) {
node = stack.pop();
if(node == p) {
return pre;
}
pre = node;
if(node.right != null) {
node = node.right;
while(node != null) {
stack.push(node);
node = node.left;
}
}
}
return null;
}
}
Convert Sorted List to Binary Search Tree
思路：jame bond 的思路，找mid的前一个点，然后两边分开找；注意middle的前后都要断开，否则会死循环；
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode sortedListToBST(ListNode head) {
if(head == null) {
return null;
}
ListNode pre = findmidpre(head);
if(pre == null || pre.next == null) {
return new TreeNode(pre.val);
} else {
ListNode middle = pre.next;
pre.next = null;
ListNode righthead = middle.next;
middle.next = null;
TreeNode root = new TreeNode(middle.val);
root.left = sortedListToBST(head);
root.right = sortedListToBST(righthead);
return root;
}
}
private ListNode findmidpre(ListNode node) {
if(node == null || node.next == null) {
return node;
}
ListNode dummpy = new ListNode(0);
dummpy.next = node;
ListNode slow = dummpy;
ListNode fast = dummpy;
while(fast != null && fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
Flatten Binary Tree to Linked List
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root: a TreeNode, the root of the binary tree
* @return: nothing
*/
public void flatten(TreeNode root) {
if(root == null) {
return;
}
flattenHelper(root);
}
private TreeNode flattenHelper(TreeNode root) {
if(root == null) {
return null;
}
TreeNode leftNode = flattenHelper(root.left);
TreeNode rightNode = flattenHelper(root.right);
if(leftNode != null) {
root.left = null;
root.right = leftNode;
TreeNode lastnode = findLastNode(leftNode);
if(lastnode != null) {
lastnode.right = rightNode;
}
}
return root;
}
private TreeNode findLastNode(TreeNode node) {
while(node != null && node.right != null) {
node = node.right;
}
return node;
}
}
Input:
1
\
2
/ \
3 4
Ouput:
[1, 3, 4, 2]
Explanation:
The root doesn't have left subtree, so the root itself is left boundary.
The leaves are node 3 and 4.
The right boundary are node 1,2,4. Note the anti-clockwise direction means you should output reversed right boundary.
So order them in anti-clockwise without duplicates and we have [1,3,4,2].
Input:
____1_____
/ \
2 3
/ \ /
4 5 6
/ \ / \
7 8 9 10
Ouput:
[1,2,4,7,8,9,10,6,3]
Explanation:
The left boundary are node 1,2,4. (4 is the left-most node according to definition)
The leaves are node 4,7,8,9,10.
The right boundary are node 1,3,6,10. (10 is the right-most node).
So order them in anti-clockwise without duplicate nodes we have [1,2,4,7,8,9,10,6,3].
思路：这题tricky的地方就是，如果从root开始收集好了，会有重复，而且left，leaves，right也会有重复。
怎么避免重复，就是分别收集root.left, root.right两个分支的left, leave, leave, right;
左右下角重复的点，全部由leave收集，左右两边边不收集root.left == null && root.right == null 的点；
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> boundaryOfBinaryTree(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
if(root == null) {
return list;
}
list.add(root.val);
collectLeft(root.left, list);
collectLeaves(root.left, list);
collectLeaves(root.right, list);
collectRight(root.right, list);
return list;
}
private void collectLeaves(TreeNode node, List<Integer> list) {
if(node == null) {
return;
}
if(node.left == null && node.right == null) {
list.add(node.val);
return;
}
collectLeaves(node.left, list);
collectLeaves(node.right, list);
}
private void collectLeft(TreeNode node, List<Integer> list) {
if(node == null || (node.left == null && node.right == null)) {
return;
}
if(node.left != null) {
list.add(node.val);
collectLeft(node.left, list);
} else {
list.add(node.val);
collectLeft(node.right, list);
}
}
private void collectRight(TreeNode node, List<Integer> list) {
if(node == null || (node.left == null && node.right == null)) {
return;
}
if(node.right != null) {
collectRight(node.right, list);
list.add(node.val);
} else {
collectRight(node.left, list);
list.add(node.val);
}
}
}
![常用的排序算法的空间复杂度和时间复杂度[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)