这几天在力扣上刷
了些二叉树的题目，依靠基础 （前序遍历~中序遍历~ 后续遍历~层序遍历）解题，当然解题方法很多。
【先将基础遍历介绍大家】
前序遍历
第一步 建立循环 因为前序遍历 (跟 左 右）先将根节点放入list中 往左侧寻找 直到左侧最后一个节点 因此左侧一路所有节点全部放入list中。
第二步 此时栈顶元素为树左侧最后一个节点 进行右树的寻找。
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> mylist = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;记录根节点
while( cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);将根节点放入栈中
mylist.add(cur.val);因为是先序(跟 左 右）将跟的值放入list中
cur = cur.left;往左边走 直达左边没有元素 此时左侧已经到最后一个节点
}
TreeNode pre = stack.pop();将栈顶元素出栈
cur = pre.right;往右边进行发展
}
return mylist;最后返回list；
}中序遍历
第一步 建立循环 因为中序遍历 ( 左 跟 右）先将根节点放入栈中 往左侧寻找 直到左侧最后一个节点 此时依次将左侧放入list中
第二步 此时栈顶元素为树左侧最后一个节点 进行右树的寻找。
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;记录跟节点
while(cur != null || !stack.empty()){
while(cur != null){
stack.push(cur );将根节点放入栈中
cur = cur.left;往左侧走 直至左侧为空
}
TreeNode pre = stack.pop();
list.add( pre.val);将此时根节点放入list中
cur = pre.right;
}
return list;
}
}层序遍历
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ret = new LinkedList<>();
Queue<TreeNode> myqueue = new LinkedList<>();
if(root == null) return ret;
myqueue.offer(root);
while(!myqueue.isEmpty()){
List<Integer> list = new LinkedList<>();
int size = myqueue.size();
while(size != 0){
TreeNode cur = myqueue.poll();
list.add(cur.val);
if(cur.left != null){
myqueue.offer(cur.left);
}
if(cur.right != null){
myqueue.offer(cur.right);
}
size--;
}
ret.add(list);
}
return ret;
}
}二叉树转为链表（力扣 114）
首先第一步 使用先序遍历 将节点值放入 链表中
第二步 计算链表长度 并使用循环将将其变换成链表的形式
class Solution {
public void flatten(TreeNode root) {
List<TreeNode> list = new ArrayList<>();
dfs(root,list);
int size = list.size();计算链表长度
for(int i = 1; i < size; i ++){使用循环
TreeNode pre = list.get(i-1)，cur = list.get(i);将第一个元素定义为pre第二个元素定义cur
pre.left = null;左侧为空
pre.right = cur; pre的右侧为cur
}
}
void dfs(TreeNode root, List<TreeNode> list ){
if(root != null){ 这边使用先序遍历
list.add(root);
dfs(root.left,list);
dfs(root.right,list);
}
}
}二叉树的下一个节点
第一步 因为pNode不是根节点 利用next找到跟节点
第二步 使用中序遍历 将节点存放进list中
第三步 遍历整个链表 利用循环 找到pNode下一个节点值
import java.util.*;
public class Solution {
LinkedList<TreeLinkNode> list = new LinkedList<>();
public TreeLinkNode GetNext(TreeLinkNode pNode) {
TreeLinkNode head = pNode;
while(head.next != null){
head = head.next;
}
search(head);
for(int i = 0 ; i < list.size(); i ++){
if(pNode == list.get(i)){
return i == list.size() -1? null: list.get(i+1);
}
}
return null;
}
public void search(TreeLinkNode pnode){
if(pnode == null) return ;
search( pnode.left);
list.add(pnode);
search( pnode.right);
}
}二叉树中和为某值的路径
基础建立在递归方法 先将根节点放入lists中 用要寻找的值减去当前节点值
递归左树和右树 直至目标值为0；并且左子树和右子树全部递归完成 才可称为完全找到一条支路。
class Solution {
List<List<Integer>> ret = new LinkedList<>();
LinkedList<Integer> lists = new LinkedList<>();
public List<List<Integer>> pathSum(TreeNode root, int target) {
dfs(root,target);
return ret;
}
public void dfs(TreeNode root,int targets){
if(root == null) return ;
lists.add(root.val);
targets -=root.val;
dfs( root.left, targets );
dfs( root.right, targets );
if(root.left == null && root.right == null && targets == 0){
ret.add(new LinkedList(lists));
}
lists.removeLast() ;
}
}把二叉树打印成多行
首先还是建立在层序遍历中 先将根节点放入队列中 找到其左侧结点或者是右侧节点 进行遍历
使用list 存放 遍历完每一层都会有放在一起 相当于数组的形式。
public class Solution {
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer> > ret = new ArrayList<>();
Queue<TreeNode> myqueue = new LinkedList<>();
if(pRoot == null) return ret;
myqueue.offer(pRoot);根节点放入其中
while(!myqueue.isEmpty()){
int size = myqueue.size();计算队列长度
ArrayList<Integer> list = new ArrayList<>();
while(size != 0){
TreeNode cur = myqueue.poll();
list.add(cur.val );节点值放入链表中
if(cur.left != null){左侧不为空时
myqueue.offer(cur.left);队列中放入
}
if(cur.right != null){右侧不为空时
myqueue.offer(cur.right);队列中放入
}
size--;
}
ret.add(list);
}
return ret;最后返回
}
}