[每日一道小算法（四十）] [二叉树] 二叉树的下一个结点（剑指offer）

╰+哭是因爲堅強的太久メ 2023-07-06 06:25 33阅读 0赞

前言：  
这道题使用两种解决解决的问题，都挺好理解的！！！

### 题目描述 ###

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

### 题目解析 ###

我首先想到的方法就是创建出中序序列，再根据中序序列来找出下一个结点。因为这里有指向父结点的指针，所以我们就可以找出根节点，找到根节点，我们就可以重建中序序列。然后就可以找出一下节点了。  
方法二的话，我们就需要找规律了。根据一个例子，我们来慢慢查找解题思路。  
以该二叉树为例，中序遍历为：\{D,B,H,E,I,A,F,C,G\}：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5Mzk3MTY1_size_16_color_FFFFFF_t_70]

1.  有右子树，下一结点是右子树中的最左结点，例如 B，下一结点是 H
2.  无右子树，且结点是该结点父结点的左子树，则下一结点是该结点的父结点，例如 H，下一结点是 E
3.  无右子树，且结点是该结点父结点的右子树，则我们一直沿着父结点追朔，直到找到某个结点是其父结点的左子树，如果存在这样的结点，那么这个结点的父结点就是我们要找的下一结点。例如 I，下一结点是 A；例如 G，并没有符合情况的结点，所以 G 没有下一结点。  
    根据这一特点我们就可以解决这个问题了，以后两种方法仅供参考。

### 代码样例 ###

#### 方法一（借助list辅助） ####

package com.asong.leetcode.TreeNext;
    
    import java.util.ArrayList;
    
    /** * 二叉树的下一个结点： * 题目描述： 给定一个二叉树和其中的一个结点，请找出中序 * 遍历书顺序的下一个结点并且返回。注意，树中的结点不仅包含 * 左右子结点，同时包含指向父结点的指针。 * * 题目解析：第一种方法，因为存在指向父结点的指针，所以我们就可以找到根节点，找到根节点， * 我们在进行中路遍历，然后再找到下一个结点就很容易了。 */
    public class Solution { 
        static ArrayList<TreeLinkNode> list = new ArrayList<TreeLinkNode>();
        public TreeLinkNode GetNext(TreeLinkNode pNode)
        { 
            TreeLinkNode root = pNode;
            while(root.next!=null)
            { 
                root = root.next;
            }
            inOrder(root);
            for (int i = 0; i < list.size(); i++) { 
                if(pNode == list.get(i))
                { 
                    //考虑最后一个结点
                    return ((i==(list.size()-1))?null:list.get(i+1));
                }
            }
            return null;
        }
        public static void inOrder(TreeLinkNode root)
        { 
            if(root==null)
            { 
                return;
            }
            inOrder(root.left);
            list.add(root);
            inOrder(root.right);
        }
    }

#### 方法二（根据特点进行求解） ####

package com.asong.leetcode.TreeNext;
    
    /** * 二叉树的下一结点 * 分为三种情况： * 1. 有右子树，下一结点是右子树中的最左结点。 * 2. 无右子树，且结点是该结点复结点的左子树，则下一结点是 * 该结点的父结点。 * 3. 无右子树，且结点是该结点父结点的右子树，则我们一直沿着父结点追朔，直到找到某个结点是其父结点的左子树， * 如果存在这样的结点，那么这个结点的父 * 结点就是我们要找的下一结点。例如 I，下一结点是 A；例如 G，并没有符合情况的结点，所以 G 没有下一结点 */
    public class Solution1 { 
        public  TreeLinkNode GetNext(TreeLinkNode pNode)
        { 
            // 1.
            if (pNode.right != null) { 
                TreeLinkNode pRight = pNode.right;
                while (pRight.left != null) { 
                    pRight = pRight.left;
                }
                return pRight;
            }
            // 2.
            if (pNode.next != null && pNode.next.left == pNode) { 
                return pNode.next;
            }
            // 3.
            if (pNode.next != null) { 
                TreeLinkNode pNext = pNode.next;
                while (pNext.next != null && pNext.next.right == pNext) { 
                    pNext = pNext.next;
                }
                return pNext.next;
            }
            return null;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5Mzk3MTY1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200216214958367.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5Mzk3MTY1,size_16,color_FFFFFF,t_70