广度优先遍历二叉树(递归二叉树遍历)

题目来自：https://www.programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html#%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E7%A7%8D%E7%B1%BB

1. 对称二叉树

101. 对称二叉树100. 相同的树572. 另一棵树的子树 2. 平衡二叉树

110. 平衡二叉树 3. 二叉树路径

257. 二叉树的所有路径404. 左叶子之和513. 找树左下角的值112. 路径总和113. 路径总和 II

递归迭代

	
	public boolean isSymmetric1(TreeNode root) {
		return compare(root.left , root.right);
	}
		
	private boolean compare(TreeNode left, TreeNode right) {
		
		if( left == null && right == null ) return true;
		if( left != null && right == null ) return false;
		if( left == null && right != null ) return false;
		if( left.val != right.val ) return false;
			
		boolean l = compare(left.left, right.right);
		boolean r = compare(left.right, right.left);
		
		return l && r;
	}
	
	
    public boolean isSymmetric3(TreeNode root) {
        Queue deque = new linkedList<>();
        deque.offer(root.left);
        deque.offer(root.right);
        while (!deque.isEmpty()) {
            TreeNode leftNode = deque.poll();
            TreeNode rightNode = deque.poll();
            if (leftNode == null && rightNode == null) {
                continue;
            }
//            if (leftNode == null && rightNode != null) {
//                return false;
//            }
//            if (leftNode != null && rightNode == null) {
//                return false;
//            }
//            if (leftNode.val != rightNode.val) {
//                return false;
//            }
            // 以上三个判断条件合并
            if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
                return false;
            }
            // 这里顺序与使用Deque不同
            deque.offer(leftNode.left);
            deque.offer(rightNode.right);
            deque.offer(leftNode.right);
            deque.offer(rightNode.left);
        }
        return true;
    }

跟上面那题做法一样

	
	public boolean isSameTree1(TreeNode p, TreeNode q) {
		if( p == null && q == null) return true;
		Queue queue = new linkedList<>();
		queue.offer(p);
		queue.offer(q);
		while(!queue.isEmpty()){

			TreeNode n1 = queue.poll();
			TreeNode n2 = queue.poll();
			if(n1 == null && n2 == null) continue;
			if(n1 == null || n2 == null || n1.val != n2.val) return false;
			//System.out.println("n1:" + n1.val + ", n2:" + n2.val);
			
			queue.offer(n1.left);
			queue.offer(n2.left);
			queue.offer(n1.right);
			queue.offer(n2.right);
		}		
		return true;
	}

	
	public boolean isSameTree(TreeNode p, TreeNode q) {
		return isSame(p, q);
	}
	public boolean isSame(TreeNode p, TreeNode q){
		if(p == null && q == null) return true;
		if(p == null || q == null || p.val != q.val) return false;
		
		boolean isl = isSame(p.left, q.left);
		boolean isr = isSame(p.right, q.right);
		
		return isl && isr;
	}

这题下线很低，上限很高

遍历每一个结点，每一个结点判断是否相等kmp算法构造哈希，埃氏筛。不是给人做的

https://leetcode-cn.com/problems/balanced-binary-tree/

递归（如果不平衡就是-1）迭代，没写

    public boolean isBalanced(TreeNode root) {
		return geth(root) != -1;
	}
	
	public int geth(TreeNode root) {
		if(root == null) return 0;
		int l = geth(root.left);
		if(l == -1) return -1;
		int r = geth(root.right);
		if(r == -1) return -1;
		if(Math.abs(l-r) > 1) return -1;		
		return Math.max(l, r) + 1;		
	}

https://leetcode-cn.com/problems/binary-tree-paths/

		
	public List binaryTreePaths(TreeNode root) {
        List result = new ArrayList<>();
        if (root == null)
            return result;
        Stack