剑指offer题解笔记：树

栏目: 数据库 · 发布时间: 6年前

内容简介：树相关的算法题在数据结构中是相对比较困难的，并且面试题也很喜欢问，基本跟链表被问的频率差不多了，所以这方面也是需要重点刷题的。题目描述：给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

剑指offer题解笔记：树

树相关的算法题在数据结构中是相对比较困难的，并且面试题也很喜欢问，基本跟链表被问的频率差不多了，所以这方面也是需要重点刷题的。

二叉树的下一个节点

题目描述：给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

其中树的结构代码如下：

public class TreeLinkNode {
   int val;
   TreeLinkNode left = null;
   TreeLinkNode right = null;
   TreeLinkNode next = null; //指向父节点

   TreeLinkNode(int val) {
       this.val = val;
   }
}

解题思路

首先，注明了是中序遍历的下一个节点，那么需要先研究中序遍历树的特征。比如如下二叉树：

剑指offer题解笔记：树

显然中序遍历结果为： 9 5 8 2 1 3 6 7 3 4 10

那么将凌乱的思路整理一下，其实我们再想一想，其实我们只需要抓住一个关键点进行突破就可以了，那就是 给定的节点是否有右子树 ，分为两种情况：

若给定的节点有右子树，如上图的节点5，那么显然5的下一个节点的值应该是8，也就是其右子树的最后一层的左子节点的值。这个实现可以使用递归获取值即可，那么这个问题就轻而易举的解决了。
另外一种情况就是给定的节点没有右子树，这个情况就比较复杂了，也很难想到（所以为啥要刷算法题，毕竟算法又不是你发明的…解决问题的思路还是得学一学的）。最简单的情况就是上面的左下角的9，显然9是没有右子树的，那么它的下一个节点实际上就是它的父节点5；最复杂的情况，就是2的右子节点1，它也没有右子树，但是它的下一个节点应该是根节点3。

所以针对上面的第二种情况，最终需要将这两种简单和复杂情况合并，那么有没有这种方法呢？

那么当然是可以有的，由于题目特别说明这个树的节点是包含指向父节点的指针的，那么根据这个特性，我们可以再思考一下：

实际上只要循环找到当前节点的父节点的左子节点等于当前节点，那么这个问题就被KO了

局部代码如下：

while (pNode.next != null) {
     TreeLinkNode parent = pNode.next;
     if (parent.left == pNode) {
         return parent;
     }
     pNode = pNode.next;
}

其中 pNode 是给定的节点，我们最终是要找 pNode 的下一个节点。

根据上述代码，对于节点9，上面显然可以得其下一个节点是5，结果正确。

对于节点1，根据上面循环往上找，最终确实找到了其下一个节点是3，结果正确。

实现代码

综合上述思路，最终可以整理代码如下：

public TreeLinkNode GetNext(TreeLinkNode pNode) {
   //如果有右子树，则找右子树的最左节点
   if (pNode.right != null) {
       TreeLinkNode node = pNode.right;
        while (node.left != null) {
             node = node.left;
        }
        return node;
   } else {
       //没有右子树，向上找第一个左链接指向的树包含该节点的祖先节点
       while (pNode.next != null) {
          TreeLinkNode parent = pNode.next;
          if (parent.left == pNode) {
              return parent;
          }
          pNode = pNode.next;
         }
     }
     return null;
}

对称二叉树

题目描述：请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

解题思路

这个题其实思路上难度不是很大，只要画个图，就可以看明白一半。

剑指offer题解笔记：树

如上图就属于题目描述的对称二叉树的一种，那么显然，只需要我们确定一个根节点下的左子节点的值和右子节点的值是否相同就可以，只要有一个不同，那么就不是对称二叉树。具体过程可以使用递归来完成。

实现代码

public boolean isSymmetrical(TreeNode pRoot) {
    if(pRoot == null){
        return true;
    }
     return isSym(pRoot,pRoot);
}

//判断是否相等
private boolean isSym(TreeNode root1,TreeNode root2){
    //如果递归中root1为null，root2不为null，那么说明不对称
    //如果root1=root2=null，那么说明递归完成后没有返回false说明完全对称，即返回true
   if(root1 == null){
      return root2 == null;
   }
    //由于上面先判断了root1==null，所以如果进入了这一步，说明root1 != null
    //但是root2先到null了，这说明存在不对称的部分，直接返回false
   if(root2 == null){
      return false;
   }
    //判断值是否相同
   if(root1.val != root2.val){
      return false;
   }
    //递归调用
   return isSym(root1.left,root2.right) && isSym(root1.right,root2.left);
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持码农网