Welcome everyone

每周一练(21)

每周一练 汪明鑫 481浏览 0评论

给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。

注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。

 

情况1:

(注:红节点即为下一节点)

 

情况2:

 

情况3:

 

情况4:

(这种情况较复杂,需要遍历父节点)

 

 

package pers.wmx.practice;

/**
 * @author: wangmingxin03
 * @date: 2020-05-18
 */
public class Practise21 {


    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        if(pNode == null) {
            return null;
        }

        //如果节点有右子树
        if(pNode.right != null){
            TreeLinkNode p = pNode.right;

            //找到右子树最左边的节点
            while(p.left != null) {
                p = p.left;
            }
            return p;
        }else{
            //如果节点无右子树

            //是其父节点的左子树
            TreeLinkNode parent = pNode.next;
            if(parent==null || parent.left == pNode) {
                return parent;
            } else{
                //是其父节点的右子树
                TreeLinkNode  pparent = parent.next;
                while(pparent != null && pparent.left != parent){
                    parent = pparent;
                    pparent = pparent.next;
                }
                return pparent;
            }
        }
    }




}

class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;   //记录父节点

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

 

 

主要考察对二叉树中序遍历的理解

 

 

转载请注明:汪明鑫的个人博客 » 每周一练(21)

喜欢 (0)

说点什么

您将是第一位评论人!

提醒
avatar
wpDiscuz