剑指offer 57 二叉树的下一个结点

题目：

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

解法一(暴力)：

思路：根据当前结点找到树的根结点，对根结点进行中序遍历，然后将遍历的每一个结点放入到集合中，最后遍历集合，找到输入的结点，后一个结点就是它的后继结点

代码实现：

public class Solution {
    
    ArrayList<TreeLinkNode> res = new ArrayList<>();
    
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        TreeLinkNode root = pNode;
        while(root.next!=null)root=root.next;
        dfs(root);
        for(int i=0;i<res.size();i++){
            if(res.get(i)==pNode&&i<res.size()-1)return res.get(i+1);
        }
        return null;
    }
    
    public void dfs(TreeLinkNode node){
        if(node==null)return;
        dfs(node.left);
        res.add(node);
        dfs(node.right);
    }
}

解法二：

如图表示中序遍历二叉树的访问顺序，根据查找后继结点的方向可以分为两类:

一、向上查找(右子结点为空) ①③⑤⑦

根据当前结点可以分为两类：

1.当前结点为父结点的左子结点 ①⑤，父结点就是后继结点，直接返回父结点

2.当前结点为父结点的右子结点 ③⑦，父结点不是后继结点，将当前结点上移指向父结点，只要满足当前结点是父结点的左子结点，当前的父结点就是后继结点，直接返回，这里会出现一个特例⑦，尾结点，向上移动过程中一直不满足当前结点是父结点的左子结点，当父结点为空时，停止查找返回null

二、向下查找(右子结点不为空) ②⑥④

根据当前结点可以分为两类：

1.右子结点的左结点为空，则后继结点为右子结点本身

2.右子结点的左结点不为空，则一直向当前结点的左子结点迭代，直到当前结点的左子结点为空，则当前结点就是后继结点

代码实现：

public class Solution {
    
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
       if(pNode==null)return null;
       if(pNode.right==null){//1,3,5,7的情况
           while(pNode.next!=null){
               TreeLinkNode root = pNode.next;
               if(root.left==pNode)return root;
               pNode = root;
           }
           return null;//7特例
       }else{//2,6,4的情况
           pNode = pNode.right;
           while(pNode.left!=null)pNode = pNode.left;
           return pNode;
       }
    }
}

剑指offer 57 二叉树的下一个结点

推荐阅读