【剑指offer】面试题8：二叉树的下一个节点

﹏ヽ暗。殇╰゛Y 2022-06-12 02:56 181阅读 0赞

## 完整代码地址 ##

[完整代码地址][Link 1]

## 题目 ##

给定一棵二叉树和其中的一个节点， 如何找出中序遍历的下一个节点？  
树中的节点除了有两个分别指向左、右节点的指针，还有一个指向父节点的指针。

public static class TreeLinkNode {
            public int val;
            public TreeLinkNode left = null;
            public TreeLinkNode right = null;
            // 指向父节点，这个名字取得不好呀，应该叫parent
            public TreeLinkNode next = null;    
            public TreeLinkNode(int val) {
                this.val = val;
            }
        }

## 思路 ##

首先判断node是否有右子树？  
└─有右子树则返回右子树中最左的节点  
└─没有右子树的话判断node是否为父节点的左子节点？  
　　└─是的话直接返回父节点  
　　└─不是的话则沿着父节点往上（parent）寻找，直到某个节点node2，node2为其父节点node3的左子节点，返回node3

## 代码 ##

public class _08_NextNodeInBinaryTrees {
        
    
        public static class TreeLinkNode {
        
            public int val;
            public TreeLinkNode left = null;
            public TreeLinkNode right = null;
            // 指向父节点，这个名字取得不好呀，应该叫parent
            public TreeLinkNode next = null;    
            public TreeLinkNode(int val) {
                this.val = val;
            }
        }
    
        /**
         * 首先判断node是否有右子树？
         *   ->有右子树则返回右子树中最左的节点
         *   没有右子树的话判断node是否为父节点的左子节点？
         *     ->是的话直接返回父节点
         *     不是的话则沿着父节点往上（parent）寻找，
         *     直到某个节点node2，node2为其父节点node3的左子节点，返回node3   
         * 
         * @param node 节点
         * @return 中序遍历的下一个节点
         */
        public TreeLinkNode GetNext(TreeLinkNode pNode) {
            if(pNode == null)
                return null;
            // 右子树不为空 
            if(pNode.right != null) {
                return findLeft(pNode.right);
            }
            // 是父节点的左子节点
            if(pNode.next != null && pNode == pNode.next.left) {
                return pNode.next;
            }
            TreeLinkNode cur = pNode;
            while(cur.next != null && cur != cur.next.left) {
                cur = cur.next;
            }
            // 遍历到了根节点还是没找到
            if(cur.next == null)
                return null;
            return cur.next;
        }
    
        private TreeLinkNode findLeft(TreeLinkNode pNode) {
            TreeLinkNode cur = pNode;
            while(cur.left != null) {
                cur = cur.left;
            }
            return cur;
        }
    }

## 测试 ##

public class _08_Test {
        
    
        public static void main(String[] args) {
            test1();
            test2();
            test3();
        }
    
        /**
         *             1
         *          /     \
         *         2       3
         *        / \     / \
         *       4   5   6   7
         *          / \      
         *         8   9
         *  
         *  有右子树：2  ->  8 
         *  没有右子树 & 为父节点的左子节点: 6  ->  3
         *  没有右子树 & 非父节点的左子节点: 7  ->  null, 9  ->  1
         *  
         *  前序：1,2,4,5,8,9,3,6,7
         *  中序：4,2,8,5,9,1,6,3,7
         */
        private static void test1() {
            TreeLinkNode n1 = new TreeLinkNode(1);
            TreeLinkNode n2 = new TreeLinkNode(2);
            TreeLinkNode n3 = new TreeLinkNode(3);
            TreeLinkNode n4 = new TreeLinkNode(4);
            TreeLinkNode n5 = new TreeLinkNode(5);
            TreeLinkNode n6 = new TreeLinkNode(6);
            TreeLinkNode n7 = new TreeLinkNode(7);
            TreeLinkNode n8 = new TreeLinkNode(8);
            TreeLinkNode n9 = new TreeLinkNode(9);
            n1.left = n2;
            n1.right = n3;
            n2.left = n4;
            n2.right = n5;
            n3.left = n6;
            n3.right = n7;
            n5.left = n8;
            n5.right = n9;
    
            n2.next = n1;
            n3.next = n1;
            n4.next = n2;
            n5.next = n2;
            n6.next = n3;
            n7.next = n3;
            n8.next = n5;
            n9.next = n5;
    
            _08_NextNodeInBinaryTrees nnibt = new _08_NextNodeInBinaryTrees();
    
            // 有右子树
            TreeLinkNode tn1 = nnibt.GetNext(n2);
            System.out.println(tn1 == n8);
    
            // 没有右子树 & 为父节点的左子节点
            TreeLinkNode tn2 = nnibt.GetNext(n6);
            System.out.println(tn2 == n3);
    
            // 没有右子树 & 非父节点的左子节点
            TreeLinkNode tn3 = nnibt.GetNext(n7);
            System.out.println(tn3 == null);
    
            // 没有右子树 & 非父节点的左子节点
            TreeLinkNode tn4 = nnibt.GetNext(n9);
            System.out.println(tn4 == n1);
        }
    
        /**
         *  只有一个节点
         */
        private static void test2() {
            _08_NextNodeInBinaryTrees nnibt = new _08_NextNodeInBinaryTrees();
            TreeLinkNode root = new TreeLinkNode(1);
            TreeLinkNode node = nnibt.GetNext(root);
            System.out.println(node == null);
        }
    
        /**
         * 树为空
         */
        private static void test3() {
            _08_NextNodeInBinaryTrees nnibt = new _08_NextNodeInBinaryTrees();
            TreeLinkNode root = null;
            TreeLinkNode node = nnibt.GetNext(root);
            System.out.println(node == null);
        }
    }

[Link 1]: https://github.com/linpeiyou/CodingInterviews