6. 二叉树的下一个节点

题目描述

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

解题思路

二叉树中序遍历顺序为 左中右

把传入的当前结点看做中结点,则:下一个节点为有两种况

  1. 当前结点的右结点为空,则下一个结点是当前节的父结点/祖先结点;
    • 当父结点的左结点等于当前结点时,当前结点的一个结点为父结点;
    • 当父结点的左结点不等于当前结点时,继续找父点的父结点;
  2. 当前结点的右结点不为空,则当前节点有右子树则下一个结点为右子树的最左结点

代码实现

java 代码

/**
 * 二叉树结点
 */
public class TreeLinkNode {
    int val; //当前结点值
    TreeLinkNode left = null;//当前结点的左结点
    TreeLinkNode right = null;//当前结点的右结点
    TreeLinkNode next = null;//当前结点的父结点

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

/**
 * 给定一个二叉树和其中的一个结点,找出中序遍历顺序的下一个结点并且返回
 * 二叉树中序遍历顺序为 左中右
 * 把传入的当前结点看做中,则:下一个节点为有两种情况
 * 1. 当前结点的右结点为空,则下一个结点是当前节点的父结点/祖先结点;
 *  - 当父结点的左结点等于当前结点时,当前结点的下一个结点为父结点;
 *  - 当父结点的左结点不等于当前结点时,继续找父结点的父结点;
 * 2. 当前结点的右结点不为空,则当前节点有右子树,则下一个结点为右子树的最左结点
 *
 * @param pNode
 * @return
 */
public TreeLinkNode getNext(TreeLinkNode pNode) {
    if (pNode.right == null) {
        while (pNode.next != null) {
            if (pNode == pNode.next.left) {
                return pNode.next;
            }
            pNode = pNode.next;
        }
        return null;
    } else {
        TreeLinkNode node = pNode.right;
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }
}

public static void main(String[] args){
    TreeLinkNode root = 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);
    node4.right = node7;
    node2.left = node4;
    root.left = node2;
    node6.left = node8;
    node3.left = node5;
    node3.right = node6;
    root.right = node3;
    System.out.println(getNext(node4).val);
}

Kotlin 代码

/**
 * 二叉树结点
 */
class TreeLinkNode(val value: Int) {
    var left: TreeLinkNode? = null //当前结点的左结点
    var right: TreeLinkNode? = null //当前结点的右结点
    var next: TreeLinkNode? = null //当前结点的父结点
}

/**
 * 给定一个二叉树和其中的一个结点,找出中序遍历顺序的下一个结点并且返回
 * 二叉树中序遍历顺序为 左中右
 * 把传入的当前结点看做中,则:下一个节点为有两种情况
 * 1. 当前结点的右结点为空,则下一个结点是当前节点的父结点/祖先结点;
 * - 当父结点的左结点等于当前结点时,当前结点的下一个结点为父结点;
 * - 当父结点的左结点不等于当前结点时,继续找父结点的父结点;
 * 2. 当前结点的右结点不为空,则当前节点有右子树,则下一个结点为右子树的最左结点
 *
 * @param pNode
 * @return
 */
private fun getNext(pNode: TreeLinkNode?): TreeLinkNode? {
    var pNode = pNode
    return if (pNode!!.right == null) {
        while (pNode!!.next != null) {
            if (pNode === pNode.next!!.left) {
                return pNode.next
            }
            pNode = pNode.next
        }
        null
    } else {
        var node = pNode.right
        while (node!!.left != null) {
            node = node.left
        }
        node
    }
}

/**
 * 入口函数
 */
fun main(args: Array<String>) {
    val root = TreeLinkNode(1)
    val node2 = TreeLinkNode(2)
    val node3 = TreeLinkNode(3)
    val node4 = TreeLinkNode(4)
    val node5 = TreeLinkNode(5)
    val node6 = TreeLinkNode(6)
    val node7 = TreeLinkNode(7)
    val node8 = TreeLinkNode(8)
    node4.right = node7
    node2.left = node4
    root.left = node2
    node6.left = node8
    node3.left = node5
    node3.right = node6
    root.right = node3
    println(getNext(node4)?.value)
}

引用声明

该题目引用自
牛客网