【上海校区】算法题(三十五):二叉树的下一个结点

python 未结 0 108
jhgjhgj
jhgjhgj 2021-07-22 14:39
悬赏:94
题目描述
给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。

分析
分情况讨论:

1.如果结点有右孩子,则返回右子树中最后一个左孩子;

2.如果结点没有右孩子,且该结点是父结点的左孩子,则返回父结点;

3.如果结点没有右孩子,且该结点是父结点的右孩子,则向上遍历父结点,返回第一个当前节点是父节点左孩子的节点

代码
public class NextOne {

        public static void main(String[] args) {
                // TODO Auto-generated method stub
                TreeLinkNode node1 = new TreeLinkNode(1);
                TreeLinkNode node2 = new TreeLinkNode(2);
                TreeLinkNode node3 = new TreeLinkNode(3);
                TreeLinkNode node4 = new TreeLinkNode(4);
                TreeLinkNode node5 = new TreeLinkNode(5);
                TreeLinkNode node6 = new TreeLinkNode(6);
                TreeLinkNode node7 = new TreeLinkNode(7);
                TreeLinkNode node8 = new TreeLinkNode(8);
                TreeLinkNode node9 = new TreeLinkNode(9);
                node6.left = node2; node6.right = node8; node2.next = node6; node8.next = node6;
               
                node2.left = node1; node2.right = node4; node8.left=node7; node8.right = node9;
                node1.next = node2; node4.next = node2; node7.next = node8; node9.next = node8;
               
                node4.left = node3; node4.right = node5; node3.next = node4; node5.next = node4;
               
                System.out.println(GetNext(node1).val);
        }
       
        //自己写的
        public static TreeLinkNode next(TreeLinkNode node){
                if(node == null){
                        return null;
                }
                TreeLinkNode lastOne = null;

                if(node.right != null){
                        lastOne = node.right;
                        TreeLinkNode temp = lastOne;
                        while(lastOne != null){
                                temp = lastOne;
                                lastOne = lastOne.left;
                        }
                        lastOne = temp;
                        return lastOne;
                }
                if(node.next.left == node){
                        return node.next;
                }
                TreeLinkNode parent = node.next;
                while(parent!=null){
                        if(parent.next.left == parent){
                                return parent.next;
                        }
                        parent = parent.next;
                }
                return null;
               
        }
        //牛客网上的
        public static TreeLinkNode GetNext(TreeLinkNode node) {
                if (node == null)
                        return null;
                if (node.right != null) { // 如果有右子树,则找右子树的最左节点
                        node = node.right;
                        while (node.left != null)
                                node = node.left;
                        return node;
                }
                while (node.next != null) { // 没右子树,则找第一个当前节点是父节点左孩子的节点
                        if (node.next.left == node)
                                return node.next;
                        node = node.next;
                }
                return null; // 退到了根节点仍没找到,则返回null
        }

}

class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

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

---------------------
作者:另一个我竟然存在
来源:CSDN
原文:https://blog.csdn.net/qq_24034545/article/details/84344309
版权声明:本文为博主原创文章,转载请附上博文链接!

相关标签:
回答
  • 消灭零回复
提交回复