查找二叉树的下一个节点

Bertha 。 2023-06-27 06:23 46阅读 0赞

[https://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e?tpId=13&tqId=11210&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tPage=3][https_www.nowcoder.com_practice_9023a0c988684a53960365b889ceaf5e_tpId_13_tqId_11210_rp_1_ru_2Fta_2Fcoding-interviews_qru_2Fta_2Fcoding-interviews_2Fquestion-ranking_tPage_3]

## 一、题目描述 ##

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

## 二、代码实现 ##

**方式一：**

用一个列表存储中序遍历序列，然后遍历该列表即可，空间O(n)，时间O(n)

/*
    public class TreeLinkNode {
        int val;
        TreeLinkNode left = null;
        TreeLinkNode right = null;
        TreeLinkNode next = null;
    
        TreeLinkNode(int val) {
            this.val = val;
        }
    }
    */
    import java.util.ArrayList;
    public class Solution {
        private static ArrayList<TreeLinkNode> list = new ArrayList<>();
    
        public TreeLinkNode GetNext(TreeLinkNode pNode)
        {
            TreeLinkNode root = pNode;
            while (root.next != null) {
                root = root.next;
            }
            
            inOrder(root, pNode);
            int i = 0;
            for (i=0; i<list.size(); i++) {
                if (list.get(i) == pNode) {
                    break;
                }
            }
            
            return (i+1 <= list.size()-1) ? list.get(i+1) : null;
        }
        
        public void inOrder(TreeLinkNode root, TreeLinkNode father) {
            if (root == null) {
                return;
            }
            
            inOrder(root.left, father);
            list.add(root);
            inOrder(root.right, father);
        }
    }

**方式二：**

不使用额外的存储空间，在中序遍历的过程中判断，空间O(1)，时间O(n)

如果目标节点为根节点，则返回其右子树最左边的一个节点/null；

如果目标节点不为根节点，

如果目标节点有右孩子，那么其右子树中最左边的一个节点/null就是中序遍历的下一个节点；

如果目标节点只有左孩子 或者 目标节点为叶子节点，我们假设目标节点的父节点为node

如果目标节点是node的左孩子，那么下一个节点就是node；

如果目标节点是node的右孩子，那么下一个节点就是node的某一个使得node在其左子树中的祖先节点（包括node）；

public TreeLinkNode GetNext(TreeLinkNode pNode)
        {
            
            TreeLinkNode father = pNode.next;    //node 或者 null
            //father==null, pNode为根节点
            if (father == null) {
                TreeLinkNode cur = pNode.right;
                while (cur != null && cur.left != null) {
                    cur = cur.left;
                }
                return cur;
            }
            
            //father!=null, pNode不为根节点，father为某个节点node
            //如果pNode有右孩子
            if (pNode.right != null) {
                TreeLinkNode cur = pNode.right;
                while (cur.left != null) {
                    cur = cur.left;
                }
                return cur;
            }
            //如果pNode没有右孩子
            //    如果pNode是father的左孩子
            if (father.left == pNode) {
                return father;
            }
            //    如果pNode是father的右孩子
            TreeLinkNode cur = father;
            while (cur.next != null && cur.next.right == cur) {
                cur = cur.next;
            }
            return cur.next;
            
        }

上面的逻辑可以简化一下：

如果目标节点有右孩子，那么其右子树最左边的节点/null就是中序遍历的下一个节点；

如果目标节点没有右孩子，我们假设目标节点的父节点为node

如果node为null，说明目标节点是根节点，此时下一个节点为null；

如果node不为null并且目标节点是node的左孩子，那么下一个节点就是node；

如果node不为null并且目标节点是node的右孩子，那么下一个节点就是node/node的某个使得node在其左子树的祖先节点；

public TreeLinkNode GetNext(TreeLinkNode pNode)
        {
            if (pNode.right != null) {
                TreeLinkNode cur = pNode.right;
                while (cur.left != null) {
                    cur = cur.left;
                }
                return cur;
            }
    
            //pNode.right == null
            TreeLinkNode father = pNode.next;    //node 或者 null
    
            if (father != null && father.left == pNode) {
                return father;
            }
            
            if (father != null && father.right == pNode) {
                TreeLinkNode cur = father;
                while (cur.next != null && cur.next.right == cur) {
                    cur = cur.next;
                }
                return cur.next;
            }
            
            //father == null
            return null;
        }

[https_www.nowcoder.com_practice_9023a0c988684a53960365b889ceaf5e_tpId_13_tqId_11210_rp_1_ru_2Fta_2Fcoding-interviews_qru_2Fta_2Fcoding-interviews_2Fquestion-ranking_tPage_3]: https://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e?tpId=13&tqId=11210&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tPage=3