统一迭代
LeetCode 144. 二叉树的前序遍历
题目链接：二叉树的前序遍历题目链接
代码
/**
* 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> result=new LinkedList<>();
Stack<TreeNode> stack=new Stack<>();
if(root!=null) stack.push(root);
while(!stack.isEmpty())
{
TreeNode node=stack.peek();
if(node!=null)
{
stack.pop();
if(node.right!=null) stack.push(node.right);
if(node.left!=null) stack.push(node.left);
stack.push(node);
stack.push(null);
}
else
{
stack.pop();
node=stack.peek();
stack.pop();
result.add(node.val);
}
}
return result;
}
}
LeetCode 94. 二叉树的中序遍历
题目链接：二叉树的中序遍历
代码
/**
* 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> inorderTraversal(TreeNode root) {
List<Integer>result=new LinkedList<>();
Stack<TreeNode>stack=new Stack<>();
if(root!=null) stack.push(root);
while(!stack.isEmpty())
{
TreeNode node=stack.peek();
if(node!=null)
{
stack.pop();
if(node.right!=null) stack.push(node.right);
stack.push(node);
stack.push(null);
if(node.left!=null) stack.push(node.left);
}
else
{
stack.pop();
node=stack.peek();
stack.pop();
result.add(node.val);
}
}
return result;
}
}
LeetCode 145. 二叉树的后序遍历
题目链接：二叉树的后序遍历题目链接
代码
/**
* 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> postorderTraversal(TreeNode root) {
List<Integer> result=new LinkedList<>();
Stack<TreeNode> stack=new Stack<>();
if(root!=null)
stack.push(root);
while(!stack.isEmpty())
{
TreeNode node=stack.peek();
if(node!=null)
{
stack.pop();
stack.push(node);
stack.push(null);
if(node.right!=null) stack.push(node.right);
if(node.left!=null) stack.push(node.left);
}
else
{
stack.pop();
node=stack.peek();
stack.pop();
result.add(node.val);
}
}
return result;
}
}
LeetCode 226. 翻转二叉树
题目链接：翻转二叉树题目链接
思路
该题目的关键就在于交换一个节点的左右孩子，所以使用前序遍历和后序遍历交换应该都可以，使用中序遍历进行交换是不可以的，因为使用中序遍历进行交换会导致某些节点交换两次。
代码
/**
* 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 TreeNode invertTree(TreeNode root) {
//前序遍历递归方法
if(root==null)
return root;
reverse(root);
invertTree(root.left);
invertTree(root.right);
return root;
}
public void reverse(TreeNode root)
{
TreeNode temp=root.left;
root.left=root.right;
root.right=temp;
}
}
/**
* 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 TreeNode invertTree(TreeNode root) {
//统一迭代法（前序遍历）
Stack<TreeNode>stack=new Stack<>();
if(root!=null) stack.push(root);
while(!stack.isEmpty())
{
TreeNode node=stack.peek();
if(node!=null)
{
stack.pop();
if(node.right!=null) stack.push(node.right);
if(node.left!=null) stack.push(node.left);
stack.push(node);
stack.push(null);
}
else
{
stack.pop();
node=stack.peek();
stack.pop();
reverse(node);
}
}
return root;
}
public void reverse(TreeNode root)
{
TreeNode temp=root.left;
root.left=root.right;
root.right=temp;
}
}
/**
* 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 TreeNode invertTree(TreeNode root) {
//迭代法（前序遍历）
Stack<TreeNode>stack=new Stack<>();
if(root!=null) stack.push(root);
while(!stack.isEmpty())
{
TreeNode node=stack.peek();
stack.pop();
reverse(node);
if(node.right!=null) stack.push(node.right);
if(node.left!=null) stack.push(node.left);
}
return root;
}
public void reverse(TreeNode root)
{
TreeNode temp=root.left;
root.left=root.right;
root.right=temp;
}
}
/**
* 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 TreeNode invertTree(TreeNode root) {
//层序遍历
ArrayDeque<TreeNode> deque=new ArrayDeque<>();
if(root!=null)
deque.offer(root);
while(!deque.isEmpty())
{
int size=deque.size();
while(size-->0)
{
TreeNode node=deque.poll();
reverse(node);
if(node.right!=null)
deque.offer(node.right);
if(node.left!=null)
deque.offer(node.left);
}
}
return root;
}
public void reverse(TreeNode node)
{
TreeNode temp=node.left;
node.left=node.right;
node.right=temp;
}
}
LeetCode 101. 对称二叉树
题目链接：对称二叉树题目链接
代码
/**
* 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 boolean isSymmetric(TreeNode root) {
if(root==null)
return true;
return compare(root.left,root.right);
}
public boolean compare(TreeNode left,TreeNode right)
{
//递归法
if(left!=null&&right==null)
return false;
if(left==null&&right!=null)
return false;
if(left==null&&right==null)
return true;
if(left.val!=right.val)
return false;
boolean compareInside=compare(left.right,right.left);
boolean compareOutside=compare(left.left,right.right);
return compareInside&&compareOutside;
}
}
/**
* 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 boolean isSymmetric(TreeNode root) {
//迭代法
Queue<TreeNode> queue=new LinkedList<>();
queue.offer(root.left);
queue.offer(root.right);
while(!queue.isEmpty())
{
TreeNode left=queue.poll();
TreeNode right=queue.poll();
if(left==null&&right==null)
continue;
if(left!=null&&right==null)
return false;
if(left==null&&right!=null)
return false;
if(left.val!=right.val)
return false;
queue.offer(left.left);
queue.offer(right.right);
queue.offer(left.right);
queue.offer(right.left);
}
return true;
}
}
LeetCode 104. 二叉树的最大深度
题目链接：二叉树的最大深度题目链接
思路
该题目可以使用递归法、回溯法、层序遍历。
代码
/**
* 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 int maxDepth(TreeNode root) {
//递归法（后序遍历）
if(root==null)
return 0;
int leftdepth=maxDepth(root.left);
int rightdepth=maxDepth(root.right);
int depth=Math.max(leftdepth,rightdepth)+1;
return depth;
}
}
/**
* 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 {
int result;
public int maxDepth(TreeNode root) {
result=0;
if(root==null)
return result;
getDepth(root,1);
return result;
}
public void getDepth(TreeNode node,int depth)
{
//回溯+前序遍历
if(depth>result)
result=depth;
if(node.left==null&&node.right==null)
return;
if(node.left!=null)
{
depth++;
getDepth(node.left,depth);
depth--;
}
if(node.right!=null)
{
depth++;
getDepth(node.right,depth);
depth--;
}
return;
}
}
LeetCode 111. 二叉树的最小深度
题目链接：二叉树的最小深度题目链接
思路
该题目可以使用递归法和层序遍历
代码
/**
* 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 int minDepth(TreeNode root) {
//递归法（后序遍历）
if(root==null)
return 0;
int left=minDepth(root.left);
int right=minDepth(root.right);
if(root.left!=null&&root.right==null)
return 1+left;
if(root.left==null&&root.right!=null)
return 1+right;
return 1+Math.min(left,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;
* }
* }
*/
class Solution {
public int minDepth(TreeNode root) {
//层序遍历
if(root==null)
return 0;
Deque<TreeNode>deque=new LinkedList<>();
deque.offer(root);
int depth=0;
while(!deque.isEmpty())
{
int size=deque.size();
depth++;
for(int i=0;i<size;i++)
{
TreeNode node=deque.poll();
if(node.left==null&&node.right==null)
return depth;
if(node.left!=null)
deque.offer(node.left);
if(node.right!=null)
deque.offer(node.right);
}
}
return depth;
}
}