剑指offer-题58：二叉树下的一个结点

待我称王封你为后i 2022-05-26 01:14 137阅读 0赞

## **题目描述** ##

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

实验平台：[牛客网][Link 1]

--------------------

## **解决思路：** ##

![这里写图片描述][70]  
![这里写图片描述][70 1]  
![这里写图片描述][70 2]

java:

/*
    public class TreeLinkNode {
        int val;
        TreeLinkNode left = null;
        TreeLinkNode right = null;
        TreeLinkNode next = null;
    
        TreeLinkNode(int val) {
            this.val = val;
        }
    }
    */
    public class Solution {
        public TreeLinkNode GetNext(TreeLinkNode pNode){
            if (pNode == null) {
                return null;
            } else {
                TreeLinkNode nextNode = null;
                if (pNode.right != null) {
                    nextNode = pNode.right;
                    while (nextNode.left != null) {
                        nextNode = nextNode.left;
                    }
                } else {
                    TreeLinkNode currentNode = pNode;
                    TreeLinkNode parentNode = pNode.next;
                    while (parentNode != null && parentNode.right == currentNode) {
                        currentNode = parentNode;
                        parentNode = currentNode.next;
                    }
                    nextNode = parentNode;
                }
                return nextNode;
            }
        }
    }

python:

略

[Link 1]: https://www.nowcoder.com/ta/coding-interviews?page=1
[70]: /images/20220526/2efa4bfe1bbf4076a21c5271b1b966b2.png
[70 1]: /images/20220526/054aaa0fe04040149a3ea1434e719f49.png
[70 2]: /images/20220526/7d9844df970b49b2824391156bbe8829.png