【java数据结构】二叉树OJ题

博客最后附有整篇博客的全部代码！！！

一、检查两颗树是否相同

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

检查两颗树是否相同
解题思路：
1.先判断两棵树是否都为空，都为空则两棵树是相等的；反之一棵树为空，另一棵树不为空，则两棵树不是相同二叉树。
2.分别进行遍历两棵树的左右节点，判断其节点的值是否相等。

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

二、另一颗树的子树

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

另一颗树的子树
解题思路1：
1.先判断SubRoot是否为空，为空则一定是子树；下来判断Root是否为空，为空则返回false。
2.自己定义了一个方法isSame（TreeNode p,TreeNode q）来判断遍历的树的左右节点的值是否相同。
3. return isSubtree(root.left,subRoot)||
4. isSubtree(root.right,subRoot)||isSame(root,subRoot);这段代码的意思：先用isSubtree(TreeNode root, TreeNode subRoot)这个方法遍历Root树的左右节点，然后每当遍历到一个节点的时候，都将该节点作为Root节点的树和SubRoot树传入到isSame（TreeNode p,TreeNode q）这个方法中进行判断这两棵树是否相同，但凡相同则返回true；反之，如果遍历完每个节点都和SubRoot树没有完全相同的树，则SubRoot就不是Root树的子树。

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(subRoot==null)return true;if(root==null)return false;return isSubtree(root.left,subRoot)||isSubtree(root.right,subRoot)||isSame(root,subRoot);}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;return isSame(p.left,q.left)&&isSame(p.right,q.right);}

三、翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

翻转二叉树
解题思路：
1.先判断Root树是否为空，为空则返回null。
2.递归树的每一个节点的左右节点，并用定义的TreeNode类型的left和right来进行接收每一个节点的左右节点。
3.最后将left和right互换。

   public TreeNode invertTree(TreeNode root) {if(root==null)return null;TreeNode left=invertTree(root.left);TreeNode right=invertTree(root.right);root.left=right;root.right=left;return root;}

四、对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

对称二叉树
解题思路：
和判断两棵树是否相同的思路相等，不同点是判断的是p的左节点和q的右节点、p的右节点和q的左节点是否相同。

    public boolean isSymmetric(TreeNode root) {if(root==null)return true;TreeNode p=root.left;TreeNode q=root.right;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;return isSame(p.left,q.right)&&isSame(p.right,q.left);}

五、判断一颗二叉树是否是平衡二叉树

给定一个二叉树，判断它是否是 平衡二叉树。

判断一颗二叉树是否是平衡二叉树

解题思路1：
时间复杂度为：O（N^2）
1.先判断树是否为空。
2.遍历每一个节点，求每一个节点的左右高度，判断该节点的左右高度差是否大于1。

       public boolean isBalanced(TreeNode root) {if(root==null)return true;int leftHight=getHeight(root.left);int rightHight=getHeight(root.right);return Math.abs(leftHight-rightHight)<=1 && isBalanced(root.left) && isBalanced(root.right);}int getHeight(TreeNode root) {if (root == null) return 0;int leftH = getHeight(root.left);int rightH = getHeight(root.right);return leftH > rightH ? leftH + 1 : rightH + 1;}

解题思路2：
时间复杂度：O（N）。
自下而上计算每个节点的高度，判断每个节点是否是平衡二叉树，如果是返回该节点的高度，反之返回-1。

    public boolean isBalanced2(TreeNode root) {return getHeight2(root)>=0;}int getHeight2(TreeNode root) {if (root == null) return 0;int leftH = getHeight2(root.left);if(leftH<0){return -1;}int rightH = getHeight2(root.right);if(rightH>=0&&Math.abs(leftH - rightH) <= 1){return Math.max(leftH, rightH) + 1;}return -1;}

六、给定一个二叉树, 找到该树中两个指定节点的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先
解题思路1：
1.先判断树是否为空，为空则返回null。
2.开始遍历树的每一个节点，找到p或q的节点，然后返回。
3.如果都找到了则返回Root节点，这里的Root节点肯定不是p或q的本身；如果没找到q节点，则公共祖先就是q节点；反之。
（此思路，当找到一个节点时，就不会继续遍历该节点的子节点）。

   public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root==null)return null;if(root==p||root==q)return root;TreeNode lefttree=lowestCommonAncestor(root.left,p,q);TreeNode righttree=lowestCommonAncestor(root.right,p,q);if(lefttree!=null&&righttree!=null){return root;}else if(lefttree!=null){return lefttree;}else{return righttree;}}

解题思路2：
1.定义两个栈s1，s2。用来保存root节点到目标节点p、q的节点数。
2.判断两个栈的长度，pop（）出栈中元素个数多的栈，让两个栈中元素个数相同。
3.peek（）两个栈栈顶元素，判断是否相同，相同则就是公共祖先；不同则pop（）出两栈顶元素。

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {Stack<TreeNode> s1=new Stack<>();Stack<TreeNode> s2=new Stack<>();getPath(root,p,s1);getPath(root,q,s2);if(s1.size()>s2.size()){int len=s1.size()-s2.size();while(len!=0){s1.pop();len--;}}else{int len=s2.size()-s1.size();while(len!=0){s2.pop();len--;}}while(!s1.isEmpty()&&!s2.isEmpty()){if(s1.peek()==s2.peek()){return s1.peek();}else{s1.pop();s2.pop();}}return null;}public boolean getPath(TreeNode root,TreeNode target,Stack<TreeNode> stack){if(root==null) return false;stack.push(root);if(root==target) return true;if(getPath(root.left,target,stack)){return true;}if(getPath(root.right,target,stack)){return true;}stack.pop();return false;}

七、根据一棵树的前序遍历与中序遍历构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

根据一棵树的前序遍历与中序遍历构造二叉树
解题思路：
1.定义一个：buildTreeChild(int[] preorder, int[] inorder,int inbegin,int inend)方法，用来构建二叉树，int[] preorder：前序遍历。 int[] inorder：中序遍历。int inbegin：标记中序遍历数组的起始位置。int inend：标记中序遍历数组的末尾。
2.定义一个私有方法：findVal(int[] inorder,int inbegin,int inend,int val)，用来在中序遍历中找到根节点的位置。此时返回的int值左边的值就是左子树，右边的值就是右子树。

 public int preIndex=0;public TreeNode buildTree(int[] preorder, int[] inorder) {return buildTreeChild(preorder,inorder,0,inorder.length-1);}public TreeNode buildTreeChild(int[] preorder, int[] inorder,int inbegin,int inend) {//这种情况下 表明 当前root 没有子树了 if(inbegin > inend) {return null;}TreeNode root = new TreeNode(preorder[preIndex]);int rootIndex = findVal(inorder,inbegin,inend,preorder[preIndex]);preIndex++;root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);return root;}private int findVal(int[] inorder,int inbegin,int inend,int val) {for(int i = inbegin ;i <= inend;i++) {if(inorder[i] == val) {return i;}}return -1;}

练习：

根据一棵树的中序遍历与后序遍历构造二叉树

八、二叉树前序非递归遍历实现

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
二叉树前序非递归遍历实现
解题思路：
1.先判断root树是否为空。
2.定义一个栈和node=root；node开始往左遍历，遍历一个将node.val放入链表中，然后将node放入栈中；当node==null时，node=stack.pop()；遍历node右边的。

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

练习：

二叉树的中序遍历非递归

练习：

二叉树的后序遍历非递归
此篇博客的全部代码！！！