114. Flatten Binary Tree to Linked List
Given a binary tree, flatten it to a linked list in-place.
For example, Given
1
/ \
2 5
/ \ \
3 4 6
The flattened tree should look like:
1
\
2
\
3
\
4
\
5
\
6
方法1—后序遍历
以图示的方式来简要说明修改过程：
2 2 2
/ \ => / \ ，4用临时变量存储 => 直到找到3的最右节点，则 / \
3 4 null 3 将4放置在3的最右节点 null 3
\
4
代码如下：
public class Solution {
public void flatten(TreeNode root) {
if(root == null){
return;
}
flatten(root.left);
flatten(root.right);
TreeNode tn = root.right;
root.right = root.left;
root.left = null;
while(root.right != null){
root = root.right;
}
root.right = tn;
}
}
方法二—使用栈dfs遍历
用栈来保存先前节点之间的关系,当从栈弹出时，可以重新定义节点之间的关系。
public class Solution {
public void flatten(TreeNode root) {
if(root == null){
return;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode tn = stack.pop();
if(tn.right != null){
stack.push(tn.right);
}
if(tn.left != null){
stack.push(tn.left);
}
if(!stack.isEmpty()){
tn.right = stack.peek();
}
tn.left = null;
}
}
}
109. Convert Sorted List to Binary Search Tree
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
方法
取中间节点作为root，将链表分为两部分，左链表对应root.left，右链表对应root.right，递归。
/**
* 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; }
* }
*/
public class Solution {
public TreeNode sortedListToBST(ListNode head) {
if(head == null){
return null;
}
return bst(head,null);
}
public TreeNode bst(ListNode head, ListNode tail){
ListNode slow = head;
ListNode fast = head;
if(head == tail){
return null;
}
while(fast.next != tail && fast.next.next != tail){
slow = slow.next;
fast = fast.next.next;
}
TreeNode root = new TreeNode(slow.val);
root.left = bst(head,slow);
root.right = bst(slow.next,tail);
return root;
}
}