1.二叉樹(shù)中和為某一值的路徑
輸入一顆二叉樹(shù)的根節(jié)點(diǎn)和一個(gè)整數(shù)景用，打印出二叉樹(shù)中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑伞插。路徑定義為從樹(shù)的根結(jié)點(diǎn)開(kāi)始往下一直到葉結(jié)點(diǎn)所經(jīng)過(guò)的結(jié)點(diǎn)形成一條路徑。(注意: 在返回值的list中舀瓢，數(shù)組長(zhǎng)度大的數(shù)組靠前)
import java.util.ArrayList;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
private ArrayList<ArrayList<Integer>> listAll = new ArrayList<ArrayList<Integer>>();
private ArrayList<Integer> list = new ArrayList<Integer>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
if (root == null) {
return listAll;
}
list.add(root.val);
target -= root.val;
if (root.left == null && root.right == null && target == 0) {
listAll.add(new ArrayList<Integer>(list));
}
FindPath(root.left, target);
FindPath(root.right, target);
list.remove(list.size() - 1);
return listAll;
}
}
target -= root.val; （更新target值）
listAll.add(new ArrayList<Integer>(list));（創(chuàng)建新的符合條件的list，否則list會(huì)指向同一個(gè)地址）
2.復(fù)雜的鏈表復(fù)制
題目描述
輸入一個(gè)復(fù)雜鏈表（每個(gè)節(jié)點(diǎn)中有節(jié)點(diǎn)值商架，以及兩個(gè)指針蛇摸，一個(gè)指向下一個(gè)節(jié)點(diǎn)，另一個(gè)特殊指針指向任意一個(gè)節(jié)點(diǎn)）揽涮，返回結(jié)果為復(fù)制后復(fù)雜鏈表的head饿肺。（注意，輸出結(jié)果中請(qǐng)不要返回參數(shù)中的節(jié)點(diǎn)引用雪标，否則判題程序會(huì)直接返回空）
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
*/
public class Solution {
public RandomListNode Clone(RandomListNode pHead)
{
if (pHead == null) {
return null;
}
CloneNew(pHead);
CloneRandom(pHead);
return Separate(pHead);
}
// 復(fù)制原鏈表村刨，原結(jié)點(diǎn)的next指向復(fù)制結(jié)點(diǎn)
private static void CloneNew(RandomListNode pHead) {
RandomListNode pNode = pHead;
while (pNode != null) {
RandomListNode pClone = new RandomListNode(pNode.label);
pClone.next = pNode.next;
pClone.random = null;
pNode.next = pClone;
pNode = pClone.next;
}
}
// 復(fù)制random
private static void CloneRandom(RandomListNode pHead) {
RandomListNode pNode = pHead;
while (pNode != null) {
RandomListNode pClone = pNode.next;
if (pNode.random != null) {
pClone.random = pNode.random.next;
}
pNode = pClone.next;
}
}
// 分離鏈表
private static RandomListNode Separate(RandomListNode pHead) {
RandomListNode pNode = pHead;
RandomListNode pCloneHead = pHead.next;
while (pNode != null) {
RandomListNode pClone = pNode.next;
pNode.next = pClone.next;
pClone.next = pClone.next == null ? null : pClone.next.next; // 偶數(shù)結(jié)點(diǎn)
pNode = pNode.next;
}
return pCloneHead;
}
}
注意復(fù)制結(jié)點(diǎn)永遠(yuǎn)是原結(jié)點(diǎn)next指針指向的結(jié)點(diǎn)
