1.用递归和非递归两种方式遍历二叉树
public static void inOrderRecur(Node head){
if(head == null){
return;
}
if(head.left != null){
inOrderRecur(head.left);
}
System.out.print(head.value);
if(head.right!= null){
inOrderRecur(head.right);
}
}
public static void preOrderRecur(Node head){
if(head == null){
return;
}
System.out.print(head.value);
if(head.left != null){
preOrderRecur(head.left);
}
if(head.right!= null){
preOrderRecur(head.right);
}
}
public static void posOrderRecur(Node head){
if(head == null){
return;
}
if(head.left != null){
posOrderRecur(head.left);
}
if(head.right!= null){
posOrderRecur(head.right);
}
System.out.print(head.value);
} 非递归
/*
前序遍历
*/
public static void preOrderUnRecur(Node head){
if(head!=null){
Stack<Node>stack = new Stack<Node>();
stack.add(head);
while (!stack.isEmpty()){
head = stack.pop();
System.out.print(head.value+" ");
if(head.right!=null){
stack.add(head.right);
}
if(head.left!=null){
stack.add(head.left);
}
}
}
System.out.println();
}
/*
中序遍历
*/
public static void inOrderUnRecur(Node head){
if(head!=null){
Stack<Node> stack = new Stack<Node>();
while (!stack.isEmpty() || head!=null){
if(head!=null){
stack.push(head);
head = head.left;
}else {
head = stack.pop();
System.out.println(head.value+" ");
head = head.right;
}
}
}
System.out.println();
}
/*
后续遍历 左右中是左中右的逆序
*/
public static void posOrderUnRecur(Node head){
if(head!=null){
Stack<Node> stack1 = new Stack<Node>();
Stack<Node> stack2 = new Stack<Node>();
stack1.push(head);
while (!stack1.isEmpty()){
head = stack1.pop();
stack2.push(head);
if(head.left!= null){
stack1.push(head.left);
}
if(head.right!=null){
stack1.push(head.right);
}
}
while (!stack2.isEmpty()){
System.out.print(stack2.pop().value+" ");
}
}
System.out.println();
} 2.序列化和反序列化二叉树
//序列化二叉树
public static String xuLieHuaErChaShu(Node head){
if(head == null){
return "#!";
}
String res = head.value+"!";
res+=xuLieHuaErChaShu(head.left);
res+=xuLieHuaErChaShu(head.right);
return res;
}
//反序列化二叉树
public static Node reconByPreString(String str){
String[] values = str.split("!");
Queue<String> queue = new LinkedList<>();
for (int i = 0; i < values.length ; i++) {
queue.add(values[i]);
}
return preOrderTree(queue);
}
public static Node preOrderTree(Queue<String>queue){
String value = queue.poll();
if(value.equals("#")){
return null;
}
Node head = new Node(Integer.valueOf(value));
head.left = preOrderTree(queue);
head.right = preOrderTree(queue);
return head;
} 3.重建二叉树
public class ReConstructBinaryTree {
/**
*输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。
* 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
* 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，
* 则重建二叉树并返回
*/
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
return reConBtree(pre,0,pre.length-1,in,0,in.length-1);
}
private TreeNode reConBtree(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd) {
if(preStart>preEnd ||inStart>inEnd){
return null;
}
//根节点
TreeNode root = new TreeNode(pre[preStart]);
for (int i = inStart; i <= inEnd ; i++) {
if(pre[preStart] == in[i]){
//重构左子树
root.left = reConBtree(pre,preStart+1,preStart+i-inStart,in,inStart,i-1);
//重构右子树
root.right = reConBtree(pre,preStart+i+1-inStart,preEnd,in,i+1,inEnd);
break;
}
}
return root;
}
}
public Node getNextNode(Node node){
if(node == null){
return node;
}
// 1. node的右子树不为null，则找右子树的最左节点
if(node.right != null){
return getLeftMost(node.right);
}else {
/*2.如果node没有右子树，那么先看node是不是node父节点的
左孩子，如果是，父节点就是他的后继节点，如果是右孩子，
就向上寻找node的后继节点，假设向上移动到的节点记为s，
s的父节点记为p，如果发现s是p的左孩子，那么节点p就是node节点的后继节点，
否则就一直向上移动*/
Node parent = node.parent;
while (parent != null && parent.left != node){
node = parent;
parent = node.parent;
}
return parent;
}
}
public Node getLeftMost(Node node){
if(node == null){
return node;
}
while (node.left != null){
node = node.left;
}
return node;
} ---
public TreeNode sortedArrayToBST(int[] nums) {
if(nums == null || nums.length == 0){
return null;
}
//包括左边界，不包括右边界
return help(nums,0,nums.length);
}
private TreeNode help(int[] nums,int start,int end){
if(start == end){
return null;
}
int mid = start + (end -start)/2;
TreeNode node = new TreeNode(nums[mid]);
node.left = help(nums,start,mid);
node.right = help(nums,mid+1,end);
return node;
}
--
public class PathSum113 {
List<List<Integer>> lists = new ArrayList<>();
public List<List<Integer>> pathSum(TreeNode root, int sum) {
if(root == null){
return lists;
}
process(root,sum,new ArrayList<>());
return lists;
}
private void process(TreeNode root, int sum, List<Integer>list){
if(root == null){
return;
}
sum -= root.val;
list.add(root.val);
if(root.left == null && root.right == null && 0 == sum){
lists.add(new ArrayList<>(list));
}
process(root.left,sum ,list);
process(root.right,sum ,list);
//java中的list传递的是引用，所以递归结束后，要把之前加入的元素删除，
list.remove(list.size()-1);
}
}
京公网安备 11010502036488号