剑指Offer的学习笔记（C#篇）-- 二叉树的下一个节点（好理解版本）

WeiMLing

发布于 2019-08-23 19:46:42

3820

发布于 2019-08-23 19:46:42

文章被收录于专栏：WeiMLing

题目描述

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

一 . 理解题意

该题目我们可以借鉴一个非常影响不好的例子来理解题意（重男轻女的思想，当然本人可不会这样，本人家庭更不会，从小被姐姐打成哈士奇）。

此外呢，该题目的关键点在于二叉树的遍历，其实这个已经说了好多次了，具体内容点这里。理解这个就好了，中序遍历嘛，就是左→根→右！

题目分析：我们把这个题目从一个“小家”出发，三个节点我们分别理解成（父节点--父母）、（左节点--儿子）、（右节点--闺女）；而该节点的下一个节点我们可以理解成该节点向下一节点的索取位置。

所以呢，这个题目就可以从两个大方向，三个小方向出发了，分别是父母（父节点），孩子（儿子和女儿），所以啊，这个题目你在分析的时候一定要夹杂着重男轻女的思想。。

1. 站在苏大强和苏妈妈的角度，有明哲、明成、明玉三个孩子，两口子这么重男轻女，肯定不会向儿子索取东西，但是如果明玉有儿子，那么大强一定要先敲诈明玉的儿子一番（步骤2，女儿就算了，大强不忍心），如果没生儿子，那就会敲诈女儿明玉（步骤4,6,7），明玉，我要三室一厅。

2. 站在儿子的角度，比如啃老族明成，压根想都不用想，直接找老爹老妈要钱！！（步骤1,3）

3. 站在女儿明玉角度想，向父母索取压根没可能，就差把你卖了，所以呢，只能找那个可以管住你爹的爹的爹了（步骤5）。当然如果不存在了，就真的没法了，只能return null；（步骤8）了。

不知道这个例子合不合适，但是蛮好理解的，但是要记住，该题目是针对中序遍历！！！！！！！如果是前序或者后续就不可以这样想了，但是依然可以通过伦理性的思维去想，哈哈哈，不举例了，怕误人子弟。

二 . 代码实现

/*
public class TreeLinkNode
{
    public int val;
    public TreeLinkNode left;
    public TreeLinkNode right;
    public TreeLinkNode next;
    public TreeLinkNode (int x)
    {
        val = x;
    }
}*/
class Solution
{
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        // write code here
        //空值鲁棒判断
        if(pNode == null)
        {
            return null;
        }
        //有女儿空，女儿有后代就要孙子，有孙女也不要，没孙子就要女儿
        if(pNode.right != null)
        {
            pNode = pNode.right;
            while(pNode.left != null)
            {
                pNode = pNode.left;
            }
            return pNode;
        }
        //没女儿的时候
        while(pNode.next != null)
        {
            //儿子啃老
            if(pNode.next.left == pNode)
            {
                return pNode.next;
            }
            //孙女找祖宗
            pNode = pNode.next;
        }
        //下个节点是空的时候，输出空
        return null;
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019-06-03 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法