Facebook 面试题 Binary tree inorder successor

电玩女神 2022-07-13 10:59 24阅读 0赞

> 给定一个二叉树，每一个结点都有指向其父节点的指针。求这个结点的inorder successor。

对于这个问题，我们首先要搞明白什么是`inorder successor`。Inorder successor指的是二叉树中序遍历后继结点，也就是中序遍历二叉树的过程中本结点的下一个结点。中序遍历最后一个结点的后继结点是`null`。  
对于二叉搜索树而言，中序后继结点就是值比本结点大的最小结点。所以如何寻找后继结点的问题是有意义的。

对于存在父指针的二叉树结点而言，寻找后继结点是不需要知道根结点的。寻找的过程存在两种情况：  
1. 本结点的右子结点不为`null`。在这种情况下我们只需找到其右子树中最左的结点即可。  
2. 本结点的右子结点为`null`。在这种情况下我们向上遍历找到后继结点。根据中序遍历的规则，向上遍历遇到的第一个是其父结点的左子结点的结点就是当前结点的后继结点。

算法的Java实现如下：

class TreeNode {
        int val;
        Node left, right, parent;
    
        Node(int val) {
            this.val = val;
            left = right = parent = null;
        }
    }
    
    public class Solution {
        public TreeNode inOrderSuccessor(TreeNode target) {
            if (n.right != null) {
                TreeNode curr = target.right;
                while (curr.left != null) {
                    curr = curr.left;
                }
                return curr;
            }
    
            //target node has no right subtree
            TreeNode curr = target;
            TreeNode p = curr.parent;
            while (p != null && curr == p.right) {
                curr = p;
                p = curr.parent;
            }
            return p;
        }
    }

--------------------

> 那么对于没有父结点的二叉树我们该如何做呢？在这种情况下我们只能解决二叉搜索树的后继结点问题。对于没有排序的二叉树来说，我们需要遍历整个树才能找到。

对于二叉搜索树而言，这个问题同样分为两种情况：  
1. 如果当前结点右子结点不为`null`,方法同上。只需要在右子树中寻找最左结点（最小值结点）。  
2. 如果当前结点右子结点为`null`，我们需要从根开始遍历。使用`2 pointer`方法，同时记录当前结点及其后继结点，当当前结点为我们的目标结点时，其后继结点也就是我们想要的结点了。

*需要注意的是这种情况下我们需要树的根结点*

Java实现如下：

public class Solution {
        public TreeNode inOrderSuccessor(TreeNode root, TreeNode target) {
            TreeNode curr = target;
            if (curr.right != null) {
                curr = curr.right;
                while (curr.left != null) {
                    curr = curr.left;
                }
    
                return curr;
            }
    
            //right subtree of target is NULL
            TreeNode succ;
            curr = root;
            while (curr != null) {
                if (curr.val > target.val) {
                    succ = curr;
                    curr = curr.left;
                } else if (curr.val < target.val) {
                    curr = curr.right;
                } else {
                    break;
                }
            }
    
            return succ;
        }
    }

这两种问题的时间复杂度都为`O(h)`，其中`h`为树的高度。因为最坏情况下我们需要遍历整个树高那么多的结点。