二叉树的前序遍历
-
@递归
public static void preOrderRecur(TreeNode head) {
if (head == null) {
return;
}
preOrderRecur(head.left);
System.out.print(head.val + " ");
preOrderRecur(head.right);
}
-
@迭代
public static void preOrderIteration(TreeNode head) {
if (head == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(head);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
System.out.print(node.val + " ");
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
}
二叉树的中序遍历
-
@递归
public static void preOrderRecur(TreeNode head) {
if (head == null) {
return;
}
System.out.print(head.val + " ");
preOrderRecur(head.left);
preOrderRecur(head.right);
}
-
@迭代
public static void inOrderIteration(TreeNode head) {
if (head == null) {
return;
}
TreeNode cur = head;
Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty() || cur != null) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
TreeNode node = stack.pop();
System.out.print(node.val + " ");
if (node.right != null) {
cur = node.right;
}
}
}
二叉树的后序遍历
-
@递归
public static void postOrderRecur(TreeNode head) {
if (head == null) {
return;
}
postOrderRecur(head.left);
postOrderRecur(head.right);
System.out.print(head.val + " ");
}
-
@迭代
/*迭代写法，利用pre记录上一个访问过的结点，与当前结点比较，
如果是当前结点的子节点，说明其左右结点均已访问，将当前结点出栈，
更新pre记录的对象。 写法(3)：取巧的方法。该写法的访问顺序并不是后序遍历，
而是利用先序遍历“根左右”的遍历顺序，
将先序遍历顺序更改为“根右左”，反转结果List，得到结果顺序为“左右根”*/
public List<Integer> postorderTraversal(TreeNode root) {//非递归写法
List<Integer> res = new ArrayList<Integer>();
if(root == null)
return res;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode pre = null;
stack.push(root);
while(!stack.isEmpty()){
TreeNode curr = stack.peek();
if((curr.left == null && curr.right == null) ||
(pre != null && (pre == curr.left || pre == curr.right))){
//如果当前结点左右子节点为空或上一个访问的结点为当前结点的子节点时，当前结点出栈
res.add(curr.val);
pre = curr;
stack.pop();
}else{
if(curr.right != null) stack.push(curr.right); //先将右结点压栈
if(curr.left != null) stack.push(curr.left); //再将左结点入栈
}
}
return res;
}
/*
//方法(3)
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if(root == null)
return res;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.pop();
if(node.left != null) stack.push(node.left);//和传统先序遍历不一样，先将左结点入栈
if(node.right != null) stack.push(node.right);//后将右结点入栈
res.add(0,node.val); //逆序添加结点值
}
return res;
}
从上到下打印二叉树
public int[] levelOrder(TreeNode root) {
Queue<TreeNode> q=new LinkedList<>();
List<Integer> res=new ArrayList<>();
if(root==null)
return new int[]{};
q.add(root);
while(!q.isEmpty())
{
TreeNode temp=q.poll();
res.add(temp.val);
if(temp.left!=null)
q.add(temp.left);
if(temp.right!=null)
q.add(temp.right);
}
int[] resf=new int[res.size()];
for(int i=0;i<res.size();i++)
{
resf[i]=res.get(i);
}
return resf;
}
从上到下打印二叉树II
public List<List<Integer>> levelOrder(TreeNode root) {
if(root==null)
return null;
List<List<Integer>> res=new ArrayList();
Queue<TreeNode> q=new LinkedList();
q.add(root);
while(!q.isEmpty())
{
List<Integer>tem=new ArrayList();
for(int i=q.size();i>0;i--)
{
TreeNode no=q.poll();
tem.add(no.val);
if(no.left!=null) q.add(no.left);
if(no.right!=null) q.add(no.right);
}
res.add(tem);
}
return res;
}
二叉树的深度
-
@迭代
public int getTreeHeight(TreeNode root){
if(null==root){
return 0;
}
ArrayDeque<TreeNode> queue=new ArrayDeque<TreeNode>();
int height=0;
queue.add(root);
while(!queue.isEmpty()){
int size=queue.size();
for(int i=0;i<size;i++){
TreeNode node=queue.removeFirst();
if(null!=node.left){
queue.add(node.left);
}
if(null!=node.right){
queue.add(node.right);
}
}
height++;
}
return height;
}
-
@递归
public int maxDepth1(TreeNode root)
{
if(root==null)
{
return 0;
}
int leftLen=maxDepth1(root.right);
int rightLen=maxDepth1(root.left);
return Math.max(leftLen,rightLen)+1;
}
image.png
-
@递归一
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//根节点到p节点的路径
List<TreeNode> path1 = new ArrayList<>();
//根节点到q节点的路径
List<TreeNode> path2 = new ArrayList<>();
getPath(root,p,path1);
getPath(root,q,path2);
TreeNode result=null;
int n = Math.min(path1.size(),path2.size());
//保留最后一个相等的节点即为公共节点
for(int i=0;i<n;i++){
if(path1.get(i)==path2.get(i))
result = path1.get(i);
}
return result;
}
//前序遍历搜索节点p或q
void getPath(TreeNode root,TreeNode node,List<TreeNode> path){
if(root==null)
return ;
path.add(root);
if(root == node)
return ;
if(path.get(path.size()-1)!=node){
getPath(root.left,node,path);
}
if(path.get(path.size()-1)!=node){
getPath(root.right,node,path);
}
if(path.get(path.size()-1)!=node){
path.remove(path.size()-1);
}
}
-
@递归二
/*
如果root是null，则说明我们已经找到最底了，返回null表示没找到
如果root与p相等或者与q相等，则返回root
如果左子树没找到，递归函数返回null，证明p和q同在root的右侧，
那么最终的公共祖先就是右子树找到的结点
如果右子树没找到，递归函数返回null，证明p和q同在root的左侧，
那么最终的公共祖先就是左子树找到的结点
*/
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null || root==p || root==q)
return root;
TreeNode leftNode=lowestCommonAncestor(root.left,p,q);
TreeNode rightNode=lowestCommonAncestor(root.right,p,q);
if(leftNode==null)
return rightNode;
if(rightNode==null)
return leftNode;
return root;
}
-
@迭代一
public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
if(root==null||root.val==p.val||root.val==q.val)
{
return root;
}
HashMap<TreeNode, TreeNode> fathers = new HashMap<>();
get_fathers1(fathers,root);
ArrayList<TreeNode> p_path=get_path1(fathers,p);
ArrayList<TreeNode> q_path =get_path1(fathers,q);
return common_tail1(p_path,q_path);
}
public void get_fathers1(HashMap fathersMap,TreeNode root){
Stack<TreeNode> fatherStack = new Stack<>();
fatherStack.push(root);
fathersMap.put(root,null);
while (!fatherStack.isEmpty())
{
TreeNode temp=fatherStack.pop();
if(temp.right!=null)
{
fatherStack.push(temp.right);
fathersMap.put(temp.right,temp);
}
if(temp.left!=null)
{
fatherStack.push(temp.left);
fathersMap.put(temp.left,temp);
}
}
}
public ArrayList<TreeNode> get_path1(HashMap<TreeNode,TreeNode> fathersMap,TreeNode target)
{
ArrayList<TreeNode> path = new ArrayList<>();
path.add(target);
while(fathersMap.get(target)!=null)
{
path.add(fathersMap.get(target));
target=fathersMap.get(target);
}
return path;
}
public TreeNode common_tail1(ArrayList<TreeNode> p_path,ArrayList<TreeNode> q_path)
{
int p=p_path.size()-1,q=q_path.size()-1;
while (p>=0&&q>=0&&p_path.get(p).val==q_path.get(q).val)
{
p--;
q--;
}
return p_path.get(p+1);
}
平衡二叉树
/*先序遍历*/
public boolean isBalanced(TreeNode root) {
if(root==null)
{
return true;
}
int lefthieght=gettreehieght(root.left);
int rightHieght=gettreehieght(root.right);
if(Math.abs(lefthieght-rightHieght)>1)
{
return false;
}
else {
return isBalanced(root.left)&&isBalanced(root.right);
}
}
public int gettreehieght( TreeNode root)
{
if(root==null)
{
return 0;
}
else
return Math.max(gettreehieght(root.left),gettreehieght(root.right))+1;
}
路径总和
int pathNumber=0;
public int pathSum(TreeNode root, int sum) {
if(root==null)
return 0;
Sum(root,sum);
pathSum(root.left,sum);
pathSum(root.right,sum);
return pathNumber;
}
private void Sum(TreeNode root, int sum) {
if(root==null)
return;
sum-=root.val;
if(sum==0)
{
pathNumber++;
}
Sum(root.right,sum);
Sum(root.left,sum);
}
