二叉树相关oj题：

对称二叉树

解题思路：判断一棵树是否轴对称，先判断左右子树结构是否相同，结构相同的情况下再判断对应的val是否轴对称，判断根节点的左右子树，再判断根节点的左右子树的左右子树是否轴对称，如此递归下去；

 * 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 isSymmetricChild(root.left,root.right);//判断左右子树是否相等

    }

    public boolean isSymmetricChild(TreeNode rootLeft,TreeNode rootRight){

       if(rootLeft==null&&rootRight!=null||rootLeft!=null&&rootRight==null){//左右子树结构不同为假

        return false;

       }

       if(rootLeft==null&&rootRight==null){//左右子树都为空，返回true

        return true;

       }

       if(rootLeft.val!=rootRight.val){//判断左右子树值是否相等

        return false;

       }

       return  isSymmetricChild(rootLeft.left,rootRight.right)&&

       isSymmetricChild(rootLeft.right,rootRight.left);//判断子树的左右子树是否对称

    }

}

 二叉树的层序遍历

题目：给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

解题思路：创建一个队列，把根节点放入队列中 ，进入队列不为空的外部循环后，求此时的队列的长度size，进入size！=0的循环，出一个，size-1，左右子树不为空就进队列;

如上述列子过程，队列进根节点一个，进入循环后就出队列，再左子树9和20进队列，9节点左右子树为空就不会进队了，出9后，出20，进15和7；

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> ret=new ArrayList<>();Queue<TreeNode> queue=new LinkedList();if(root==null){return ret;}queue.offer(root);TreeNode cur= null;while (!queue.isEmpty()){List list=new ArrayList<>();int size= queue.size();while (size!=0){cur= queue.peek();TreeNode cur1=queue.poll();list.add(cur1.val);if(cur.left!=null){queue.offer(cur.left);}if(cur.right!=null){queue.offer(cur.right);}size--;}ret.add(list);}return ret;}
}

二叉树的最近公共祖先

题目：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

 代码：

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root==null){return root;}if(root==p||root==q){return root;}TreeNode leftT=lowestCommonAncestor(root.left,p,q);TreeNode rightT=lowestCommonAncestor(root.right,p,q);if(leftT!=null&&rightT!=null){return root;}else if(leftT!=null){return leftT;}else if(rightT!=null){return rightT;}return null;}
}

二叉树的前序遍历（非递归）

代码：

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> list=new ArrayList<>();if(root==null){return list;}Stack<TreeNode> stack=new Stack<>();TreeNode cur=root;while (cur!=null||!stack.isEmpty()){while (cur!=null){stack.push(cur);list.add(cur.val);cur=cur.left;}cur=stack.pop();cur=cur.right;}return list;}
}

根据二叉树创建字符串

代码：

class Solution {public String tree2str(TreeNode root) {StringBuilder stringBuilder=new StringBuilder();tree2strChild(root,stringBuilder);return stringBuilder.toString();}private String tree2strChild(TreeNode root,StringBuilder stringBuilder) {if(root==null){return null;}stringBuilder.append(root.val);if(root.left!=null){stringBuilder.append("(");tree2strChild(root.left,stringBuilder);stringBuilder.append(")");}else {if(root.right==null) {return null;}else {stringBuilder.append("()");}}if(root.right!=null){stringBuilder.append("(");tree2strChild(root.right,stringBuilder);stringBuilder.append(")");}else{return null;}return stringBuilder.toString();}}