題目：

一個普通二叉樹，如何找到兩個給定節點之間的距離？ ，其中二叉樹中每個結點的值都不相同

思路：兩個節點之間的最短路徑一定會經過兩個節點的最小公共祖先，所以我們可以用LCA（最低公共祖先）的解法。不同于LCA的是，我們返回不只是標記，而要返回從目標結點遞歸回當前節點的路徑。當遇到最小公共祖先的時候便合并路徑。需要注意的是，我們要單獨處理目標節點自身是最小公共祖先的情況。

代碼1：

#include <iostream> #include <vector> #include <queue>using namespace std;struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x):val(x), left(nullptr), right(nullptr){} };/*用于判斷節點值是不是在這個子樹上，并求對應的距離*/ bool hasNode(TreeNode* root, int num, int &len) {if (root == nullptr)return false;queue<TreeNode* > que;que.push(root);while (!que.empty()){++len;int size = que.size();while (size){root = que.front(); que.pop();if (root->val == num)return true;if (root->left != nullptr)que.push(root->left);if (root->right != nullptr)que.push(root->right);--size;}}return false; }int shortestDistance(TreeNode* root, int num1, int num2) {if (root == nullptr)return 0;queue<TreeNode* > que;que.push(root);while (!que.empty()){int size = que.size();while (size){root = que.front(); que.pop();if (root->left != nullptr)que.push(root->left);if (root->right != nullptr)que.push(root->right);/* 如果一個節點是另一個節點的祖節點，則用下面這兩個if求解*/if (root->val == num1){int left = 0;if (hasNode(root->left, num2, left))return left;int right = 0;if (hasNode(root->right, num2, right))return right;}if (root->val == num2){int left = 0;if (hasNode(root->left, num1, left))return left;int right = 0;if (hasNode(root->right, num1, right))return right;}/*下面的代碼是兩個節點有共同的祖節點，但兩個節點不在從根結點到葉結點的同一條路徑上*/int left1 = 0;int right1 = 0;if (hasNode(root->left, num1, left1) && hasNode(root->right, num2, right1)){return left1 + right1;}elsecontinue;int left2 = 0;int right2 = 0;if (hasNode(root->left, num2, left2) && hasNode(root->right, num1, right2)){return left2 + right2;}}}return 0; }int main() {TreeNode* root = new TreeNode(1);TreeNode* node1 = new TreeNode(2);TreeNode* node2 = new TreeNode(3);TreeNode* node3 = new TreeNode(4);TreeNode* node4 = new TreeNode(5);TreeNode* node5 = new TreeNode(6);TreeNode* node6 = new TreeNode(7);root->left = node1;root->right = node2;node1->left = node3;node1->right = node4;node2->left = node5;node2->right = node6;cout << shortestDistance(root, 4, 1) << endl;return 0; }

代碼2：

int high(TreeNode* root, int num1, int num2) {if (root == nullptr)return 0;queue<TreeNode* > que;que.push(root);int level = 0;while (!que.empty()){++level;int size = que.size();while (size != 0){root = que.front(); que.pop();if (root->val == num1 || root->val == num2){return level;}if (root->left != nullptr)que.push(root->left);if (root->right != nullptr)que.push(root->right);--size;}}return 0; }int shortestDistance(TreeNode* root, int num1, int num2) {if (root == nullptr || num1 == num2)return 0;queue<TreeNode* > que;que.push(root);while (!que.empty()){root = que.front();que.pop();if (root->val == num1 || root->val == num2){return high(root->left, num1, num2) + high(root->right, num1, num2);}if (high(root->left, num1, num2) > 0 && high(root->right, num1, num2) > 0){return high(root->left, num1, num2) + high(root->right, num1, num2);}if (root->left != nullptr)que.push(root->left);if (root->right != nullptr)que.push(root->right);}return 0; }

總結

以上是生活随笔為你收集整理的二叉树中任意两个节点的距离的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。