牛客NC279 二叉树的下一个结点【中等二叉树中序遍历 C++/Java/Go/PHP】

题目

在这里插入图片描述

题目链接：
https://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e

思路

思路：我们首先要根据给定输入中的结点指针向父级进行迭代，
直到找到该树的根节点；然后根据根节点进行中序遍历，当遍历到和给定树节点相同的节点时，
下一个节点就是我们的目标返回节点
具体做法：step 1：首先先根据当前给出的结点找到根节点
step 2：然后根节点调用中序遍历
step 3：将中序遍历结果存储下来
step 4：最终拿当前结点匹配是否有符合要求的下一个结点

参考答案C++

/*
struct TreeLinkNode {int val;struct TreeLinkNode *left;struct TreeLinkNode *right;struct TreeLinkNode *next;TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {}
};
*/
class Solution {public:TreeLinkNode* GetNext(TreeLinkNode* pNode) {//第一步：找到根节点TreeLinkNode* root = pNode;while (root->next != nullptr) {root = root->next;}//中序遍历找到pNode的下一个节点vector<TreeLinkNode*> stk;TreeLinkNode* prev = nullptr;while (stk.size() > 0 || root != nullptr) {while (root != nullptr) {stk.push_back(root);root = root->left;}int size = stk.size();root = stk[size - 1];if (prev != nullptr && prev == pNode) {return root;}vector<TreeLinkNode*> stkbak;for (int i = 0; i < size - 1; i++) {stkbak.push_back(stk[i]);}prev = root;root = root->right;stk = stkbak;}return nullptr;}
};

参考答案Java

import java.util.*;
/*
public class TreeLinkNode {int val;TreeLinkNode left = null;TreeLinkNode right = null;TreeLinkNode next = null;TreeLinkNode(int val) {this.val = val;}
}
*/
public class Solution {public TreeLinkNode GetNext(TreeLinkNode pNode) {/*思路：我们首先要根据给定输入中的结点指针向父级进行迭代，直到找到该树的根节点；然后根据根节点进行中序遍历，当遍历到和给定树节点相同的节点时，下一个节点就是我们的目标返回节点具体做法：step 1：首先先根据当前给出的结点找到根节点step 2：然后根节点调用中序遍历step 3：将中序遍历结果存储下来step 4：最终拿当前结点匹配是否有符合要求的下一个结点*///先找到根节点TreeLinkNode root = pNode;while (root.next != null) root = root.next;//中序遍历Stack<TreeLinkNode> stk = new Stack<>();TreeLinkNode pre = null;while (!stk.isEmpty() || root != null) {while (root != null) {stk.add(root);root = root.left;}root = stk.pop();if (pre != null && pre == pNode) {return root;}pre = root;root = root.right;}return null;}
}

参考答案Go

package main/*
type TreeLinkNode struct {Val intLeft *TreeLinkNodeRight *TreeLinkNodeNext *TreeLinkNode
}
*/func GetNext(pNode *TreeLinkNode) *TreeLinkNode {//第一步：先找到根节点root := pNodefor root.Next != nil {root = root.Next}//中序遍历找到pNode的下一个节点stk := []*TreeLinkNode{}var prev *TreeLinkNode = nilfor len(stk) > 0 || root != nil {for root != nil {stk = append(stk, root)root = root.Left}size := len(stk)root = stk[size-1]stkbak := []*TreeLinkNode{}for i := 0; i < size-1; i++ {stkbak = append(stkbak, stk[i])}if prev != nil && prev == pNode {return root}prev = rootstk = stkbakroot=root.Right}return nil
}

参考答案PHP

<?php
/*class TreeLinkNode{var $val;var $left = NULL;var $right = NULL;var $next = NULL;function __construct($x){$this->val = $x;}
}*/
function GetNext($pNode)
{//第一步：找到根节点$root = $pNode;while ($root->next!=null) {$root = $root->next;}//中序遍历找到pNode的下一个节点$stk = [];$prev = null;while (count($stk) >0 || $root!=null){while ($root!=null){$stk[count($stk)] = $root;$root = $root->left;}$root = array_pop($stk);if($prev!=null && $prev ==$pNode){return $root;}$prev = $root;$root =$root->right;}return null;
}