/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
//初识二叉树,lchild、data、rchild
//拆分成单个二叉树,树叶高度呢都代表1
//深度优先遍历实际上就是前序遍历
//DFS max(l,r)+1
class Solution {
public int maxDepth(TreeNode root) {
if (root != null) {
int leftHeight = maxDepth(root.left);
int rightHeight = maxDepth(root.right);
return Math.max(leftHeight, rightHeight) + 1;
}
return 0;
}
}
//BFS
//boolean offer(E e)方法-----向队列末尾追加一个元素
//E poll()方法-----从队首获取元素。注意,获取后该元素就从队列中被移除了!出队操作
//E peek()方法-----同样可以获取队首元素,但是与poll不同的是并不会将该元素从队列中删除。
//层次遍历的代码比較简单。仅仅须要一个队列就可以。先在队列中增加根结点。之后对于随意一个结点来说。
//在其出队列的时候,訪问之。同一时候假设左孩子和右孩子有不为空的。入队列。
//二叉树的BFS遍历
// class Solution {
// public void BFS(TreeNode root) {
// if (root != null) {
// Queue<TreeNode> queue = new LinkedList<>();
// queue.offer(root);
// while (queue.size() != 0) {
// //就是让root入队列,出队列的时候取名为node,然后继续递归。
// //好好理解理解,到了这个时候了,应该很简单
// //你从队列中出去的时候,得把名字留下啊,让下一个在队列中得叫这个名字,
// //才能循环的起来啊
// //换名字是因为弹出来的重名了。
// TreeNode node = queue.poll();
// System.out.print(node.val);
// if (node.left != null) {
// queue.offer(node.left);
// }
// if (node.right != null) {
// queue.offer(node.right);
// }
// }
// }
// }
// }
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
//这里面其实有很多话想说,接下来就要开始理解递归了。
//可以看到在使用了静态递归方法后,并没有什么返回值吧,而是将里面的类似res这样的值改变最后输出。
// class Solution {
// public List<Integer> inorderTraversal(TreeNode root) {
// List<Integer> res = new ArrayList<>();
// LDR(root, res);
// return res;
// }
// public void LDR(TreeNode root, List<Integer> res) {
// if (root == null) {
// return;
// }
// LDR(root.left);
// res.add(root.val);
// LDR(root.right);
// }
// }
//非递归的方式实现二叉树的中序遍历
//左左左左(代表的是此时的中,上一步的左,这一步还要继续右,假如右没有,继续退到上一步的中,以此类推
//每次都永远是以中值得情况输出得
// class Solution {
// public List<Integer> inorderTraversal(TreeNode root) {
// LinkedList<TreeNode> stack = new LinkedList<>();
// //这边不需要换名字的啊,你弹出来的时候换名字就好啊、。。。。菜鸡
// //TreeNode tempNode = root;
// while (tempNode != null || !stack.isEmpty()) {
// if (tempNode != null) {
// stack.push(tempNode);
// tempNode = tempNode.left;
// } else {
// //将这个输出,往右跑,bingo
// TreeNode tempNode = stack.pop();
// System.out.println(tempNode.val);
// tempNode = tempNode.right;
// }
// }
// }
// }
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
Deque<TreeNode> stack = new LinkedList<TreeNode>();
while (root != null || !stack.isEmpty()) {
if (root != null) {
stack.push(root);
root = root.left;
} else{
root = stack.pop();
res.add(root.val);
root = root.right;
}
}
return res;
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
//这个BFS不是一个递归啊。。别搞蒙蔽啊
// class Solution {
// public List<List<Integer>> levelOrder(TreeNode root) {
// List<List<Integer>> res = new ArrayList<>();
// //反正一直往左找完了往右找,找个机会弹呗
// BFS(root, res);
// return res;
// }
// public void BFS(TreeNode root, List<List<Integer>> res) {
// if (root == null) return;
// LinkedList<TreeNode> queue = new LinkedList<>();
// queue.offer(root);
// while (queue.size() != 0) {
// int n = queue.size();
// List<Integer> re = new ArrayList<>();
// for (int i = 0; i < n; i++){
// TreeNode temp = queue.poll();
// re.add(temp.val);
// if (temp.left != null) {
// queue.offer(temp.left);
// }
// if (temp.right != null) {
// queue.offer(temp.right);
// }
// }
// res.add(re);
// }
// }
// }
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
//BFS是横着放啊。
if (root == null) return res;
LinkedList<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (queue.size() != 0) {
int n = queue.size();
List<Integer> re = new ArrayList<>();
for (int i = 0; i < n; i++){
TreeNode temp = queue.poll();
re.add(temp.val);
if (temp.left != null) {
queue.offer(temp.left);
}
if (temp.right != null) {
queue.offer(temp.right);
}
}
res.add(re);
}
return res;
}
}
// public List<List<Integer>> levelOrder(TreeNode root) {
// List<List<Integer>> res = new ArrayList<>();
// Queue<TreeNode> queue = new ArrayDeque<>();
// if (root != null) {
// queue.add(root);
// }
// while (!queue.isEmpty()) {
// int n = queue.size();
// List<Integer> level = new ArrayList<>();
// for (int i = 0; i < n; i++) {
// TreeNode node = queue.poll();
// level.add(node.val);
// if (node.left != null) {
// queue.add(node.left);
// }
// if (node.right != null) {
// queue.add(node.right);
// }
// }
// res.add(level);
// }
// return res;
// }
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
//这个写法是对的,依据BFS分层每层都是一个集合的写法(上一个题解)。
//暂且认为满二叉树的时候可以这么写吧,就是没null的时候。
// class Solution {
// public boolean isSymmetric(TreeNode root) {
// if (root == null) return true;
// LinkedList<TreeNode> queue = new LinkedList<>();
// TreeNode t = new TreeNode(-1);
// boolean flag = false;
// queue.offer(root);
// while (!queue.isEmpty()) {
// int n = queue.size();
// List<Integer> re = new ArrayList<>();
// for (int i = 0; i < n; i++) {
// TreeNode node = queue.poll();
// re.add(node.val);
// //注意为null的情况
// if (node.left != null) {
// queue.offer(node.left);
// } else {
// queue.offer(t);
// }
// if (node.right != null) {
// queue.offer(node.right);
// } else {
// queue.offer(t);
// }
// }
// //集合中的对称元素
// for (int i = 0; i < n/2; i++) {
// if (re.get(i) == re.get(n - i -1)) {
// //来一次判断一次,打个标记就行
// flag = true;
// } else {
// flag = false;
// }
// }
// }
// return flag;
// }
// }
//递归或者迭代,在找一个树用来做对称
//很重要的一点,就是null的时候是怎么回事。
//应该是null也算一个TreeNode了,也入队列了,弹出来也是null,
//但是不能在继续指left或者right,不然就是空指针异常了
class Solution {
public boolean isSymmetric(TreeNode root) {
return check(root, root);
}
public boolean check(TreeNode u, TreeNode v) {
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(u);
queue.offer(v);
while (!queue.isEmpty()) {
u = queue.poll();
v = queue.poll();
if (u == null && v == null) {
continue;
}
if ((u == null || v == null) || (u.val != v.val)) {
return false;
}
queue.offer(u.left);
queue.offer(v.right);
queue.offer(u.right);
queue.offer(v.left);
}
return true;
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
DLR(root, res);
return res;
}
public void DLR(TreeNode root, List<Integer> res) {
if (root != null) {
res.add(root.val);
DLR(root.left, res);
DLR(root.right, res);
}
}
}