Java实现Leetcode题（二叉树-2）

Leetcode226(翻转二叉树)

package tree;

import java.util.Deque;
import java.util.LinkedList;

public class LeetCode226 {
	public static void main(String[] args) {
		System.out.print("待定");
	}

	//递归
	public static void invertTree(TreeNode root) {
		if(root==null) {
			return;
		}
		swap(root);
		invertTree(root.left);
		invertTree(root.right);
	}
	public static void swap(TreeNode root) {
		TreeNode temp = root.right;
		root.right = root.left;
		root.left = temp;
	}
	//迭代
	public static void invertTree02(TreeNode root) {
		Deque<TreeNode> de = new LinkedList<>();
		if(root ==null) {
			return;
		}
		de.addFirst(root);
		while(!de.isEmpty()) {
			TreeNode temp = de.peekFirst();
			swap(temp);
			de.pollFirst();
			de.addFirst(temp.right);
			de.addFirst(temp.left);
		}
	}
}

Leetcode101(对称二叉树)

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return compare(root.left,root.right);
    }
    public static boolean compare(TreeNode left,TreeNode right) {
		if(left==null&&right!=null)return false;
		else if(right==null&&left!=null)return false;
		else if(right==null&&left==null)return true;
		else if(left.val!=right.val)return false;
		
		boolean outsize = compare(left.left,right.right);
		boolean insize = compare(left.right,right.left);
		return outsize&&insize;
	}
    //迭代法
     public boolean isSymmetric(TreeNode root) {
       if(root==null) {
			return true;
		}
		Deque<TreeNode> de = new LinkedList<>();
		de.addLast(root.left);
		de.addLast(root.right);
		while(!de.isEmpty()) {
			TreeNode left = de.peekFirst();
			de.pollFirst();
			TreeNode right = de.peekFirst();
			de.pollFirst();
			if(left==null&&right==null) {
				continue;
			}
			if(left==null||right==null||(left.val!=right.val)) {
				return false;
			}
			de.addLast(left.left);
			de.addLast(right.right);
			de.addLast(left.right);
			de.addLast(right.left);
		}
		return true;
    }
    
}

Leetcode222（完全二叉树的节点数）?

package tree;

public class Leetcode222 {
	public static int getCount(TreeNode root) {
		if(root==null) {
			return 0;
		}
		int leftNum = getCount(root.left);
		int rightNum = getCount(root.right);
		return leftNum+rightNum+1;
	}
	
}

Leetcode110（平衡二叉树）?

public class LeetCode110 {
	public boolean isBalanced(TreeNode root) {
		if(getDepth(root)!=-1) {
			return true;
		}
		return false;
		
    }
	
	public static int getDepth(TreeNode root) {
		if(root==null) {
			return 0;
		}
		int leftDepth = getDepth(root.left);
		if(leftDepth==-1) {
			return -1;
		}
		int rightDepth = getDepth(root.right);
		if(rightDepth==-1) {
			return -1;
		}
		int result;
		if(Math.abs(rightDepth-leftDepth)>1) {
			 result=-1;
		}else {
			result=Math.max(rightDepth, leftDepth)+1;
		}
		return result;
	}
}

Leetcode257（二叉树的所有路径）

package tree;

import java.util.ArrayList;
import java.util.List;

public class Leetcode257 {
	public static List<String> findWay(TreeNode root){
		List<String> res = new ArrayList<>();
		if(root==null) {
			return res;
		}
		List<Integer> path = new ArrayList<>();
		travelWay(root,path,res);
		return res;
	}
	public static void travelWay(TreeNode root,List<Integer> path,List<String> res){
		path.add(root.val);
		if(root.left==null&&root.right==null) {
			StringBuffer str = new StringBuffer();
			for(int i =0;i<path.size()-1;i++) {
				str.append(path.get(i)).append("->");
			}
			str.append(path.get(path.size()-1));
			res.add(str.toString());
			return;
		}
		if(root.left!=null) {
			travelWay(root.left,path,res);
			path.remove(path.size()-1);
		}
		if(root.right!=null) {
			travelWay(root.right,path,res);
			path.remove(path.size()-1);
		}
		
	}
}

Leetcode404（左叶子结点之和）

package tree;

import java.util.Deque;
import java.util.LinkedList;

public class LeetCode404 {
	public int sumOfLeftLeaves(TreeNode root) {
		if(root==null) {
			return 0;
		}
		int leftNum = sumOfLeftLeaves(root.left);
		if(root.left!=null&&root.left.left==null&&root.left.right==null) {
			leftNum = root.left.val;
		}
		int rightNum = sumOfLeftLeaves(root.right);
		int sum=leftNum+rightNum;
		return sum;
    }
	//迭代
	public int sumOfLeftLeaves1(TreeNode root) {
		if(root==null) {
			return 0;
		}
		Deque<TreeNode> de = new  LinkedList<>();
		de.addFirst(root);
		int res = 0;
		while(!de.isEmpty()) {
			TreeNode temp = de.pollFirst();
			if(temp.left!=null&&temp.left.left==null&&temp.left.right==null) {
				res+=temp.left.val;
			}
			if(temp.right!=null) {
				de.addFirst(temp.right);
			}
			if(temp.left!=null) {
				de.addFirst(temp.left);
			}
		}
		return res;
    }
	//层序
	public int sumOfLeftLeaves2(TreeNode root) {
		if(root==null) {
			return 0;
		}
		Deque<TreeNode> de = new  LinkedList<>();
		de.add(root);
		int result = 0;
		while(!de.isEmpty()) {
			int size = de.size();
			while(size-->0) {
				TreeNode temp = de.pollFirst();
				if(temp.left!=null) {
					if(temp.left.left==null&&temp.left.right==null) {
						result+=temp.left.val;
					}
					de.addLast(temp.left);
				}
				if(temp.right!=null) {
					de.addLast(temp.right);
				}
			}
		}
		return result;
	}
}

Leetcode513(树左边的值)

public class LeetCode513 {
	public int findLeftNum(TreeNode root) {
		if(root==null) {
			return 0;
		}
		Deque<TreeNode> de = new LinkedList<>();
		int result=0;
		de.add(root);
		while(!de.isEmpty()) {
			int size = de.size();
			result = de.peekFirst().val;
			while(size-->0) {
				TreeNode temp = de.pollFirst();
				if(temp.left!=null) {
					de.addLast(temp.left);
				}
				if(temp.right!=null) {
					de.addLast(temp.right);
				}
			}
		}
		return result;
		
	}
}

?