黑马程序员技术交流社区

标题: 【上海校区】算法题（三十五）：二叉树的下一个结点 [打印本页]

---

作者: 梦缠绕的时候    时间: 2018-11-26 09:17
标题: 【上海校区】算法题（三十五）：二叉树的下一个结点
题目描述
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

分析
分情况讨论：

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
版权声明：本文为博主原创文章，转载请附上博文链接！

---

作者: 不二晨    时间: 2018-11-28 15:48
奈斯

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2