死磕二叉樹

• 近一年都比較關注算法相關的知識，也刷了不少題，之前的文章中大多也是算法相關的文章，但是感覺每次遇到樹相關的題型都不能應對自如，因此還是有必要在相關知識上下功夫，因此有此次總結，以下是所有樹相關的文章

數據結構與算法–面試必問AVL樹原理及實現

數據結構與算法–二叉樹的深度問題

數據結構與算法–二叉堆（最大堆，最小堆）實現及原理

數據結構與算法–二叉查找樹轉順序排列雙向鏈表

數據結構與算法-- 二叉樹中和為某一值的路徑

數據結構與算法-- 二叉樹后續遍歷序列校驗

數據結構與算法-- 廣度優先打印二叉樹

數據結構與算法–解決問題的方法- 二叉樹的的鏡像

數據結構與算法–重建二叉樹

數據結構與算法–二叉查找樹實現原理

數據結構與算法–二叉樹實現原理

數據結構與算法–B樹原理及實現

數據結構與算法–數字在排序數組中出現次數

數據結構與算法–死磕二叉樹

數據結構與算法–二叉樹第k個大的節點

• 本文中樹，二叉樹的實現都用自己的實現方式，在以上列舉的最后兩篇文中有詳細的說明
  

• 二叉樹，或者是說樹經常用于大量的輸入數據的場景下。大部分的操作運行時間平均是O(logN)。

• 二叉樹的變種題型多如牛毛，還是要掌握方法，多看不同題型，訓練知識遷移的能力，如下題：

題目：輸入一棵二叉樹和他的兩個節點，求他們的最低公共祖先。

• 最低公共祖先的定義：給定一個有根樹T 時候，對于任意兩個節點 U， V，找到一個離根最遠的節點X， 使得X同時 是U ， V 的祖先，那么X便是 U，V的最近公共祖先。

最簡模式

• 上題中并沒有明顯給出樹的特性，只是強調了一棵二叉樹，那么我們用二叉搜索樹為案例來分析如下：
  • 需要找到最低公共祖先，也就是找父節點，二叉樹節點的特性，父節點比左節點大，比右節點小
  • 那么會有幾種情況，如果兩個節點分布在多個分支，那么我們需要找的父節點大小必然介于 V，U之間，情況一
  • 如果二叉樹是一個單鏈，那么我們需要找到 V，U的其中一個父節點，此時改父節點要不不UV都打，要么比UV都小，情況二
  • 用如下圖表示：
    

• 如上所示的一顆二叉搜索樹，當輸入的是6, 8 時候，公共祖先就是7 ，介于6， 8 之間

• 如果輸入的是3， 4,公共祖先就是2， 比3,4 都要小，或者反過來都在左子樹，那么比輸入值都大

• 經過如上分析，那么我們直接中序遍歷樹，每次得到節點與輸入節點比較，如果介于 UV之間，則返回得到我們需要的節點

• 如果寫范問節點同時大于U，V，并且是U，或者V的父節點，那么該節點也是我們需要的節點

• 如上分析有如下代碼：

/*** 輸入兩個樹的節點node1， node2，找到他們最低公共祖先.* 最近公共祖先的定義為：對于有根樹 T 的兩個結點 p、q，最近公共祖先表示為一個結點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節點也可以是它自己的祖先）。** @author liaojiamin* @Date:Created in 16:31 2021/7/9*/ public class FindCommonNode {public static void main(String[] args) {BinaryNode node = new BinaryNode(null, null, null);BinarySearchTree searchTree = new BinarySearchTree();Random random = new Random();for (int i = 0; i < 10; i++) {node = searchTree.insert(random.nextInt(100), node);}BinaryNode node1 = new BinaryNode(29, null, null);node = searchTree.insert(node1, node);BinaryNode node2 = new BinaryNode(45, null, null);node = searchTree.insert(node2, node);BinaryNode result = findBinarySearchTree(node, node1, node2);System.out.println(result.getElement());}/*** 二叉排序樹解法*/public static BinaryNode findBinarySearchTree(BinaryNode tree, BinaryNode node1, BinaryNode node2) {if (tree == null || node1 == null || node2 == null) {return null;}// node1< tree < node2if (node1.compareTo(node2) < 0 && tree.compareTo(node1) > 0 && tree.compareTo(node2) < 0) {return tree;}// node2< tree < node1if (node1.compareTo(node2) > 0 && tree.compareTo(node1) < 0 && tree.compareTo(node2) > 0) {return tree;}if (tree.compareTo(node1) > 0 & tree.compareTo(node2) > 0) {if (tree.getLeft() == node1 || tree.getLeft() == node2) {return tree;}return findBinarySearchTree(tree.getLeft(), node1, node2);}if (tree.compareTo(node1) < 0 & tree.compareTo(node2) < 0) {if (tree.getRight() == node1 || tree.getRight() == node2) {return tree;}return findBinarySearchTree(tree.getRight(), node1, node2);}return null;} }

困難模式

• 如果不是二叉排序樹，只是一個普通的樹或者二叉樹，并且樹中沒有指向父節點的指針

• 分析如下：

  • 不能用比較的方式找父節點，那么用遍歷，兩個節點都出現在某個節點的子節點，或者直接在某個節點下，如情況一：

• 6， 8 都出現在了7 節點下，但是同時也都出現在了5 節點的子節點下

• 我們需要求解的是最低公共祖先，那么離根節點越遠的父節點才是我們需要求解的

• 我們可以從根遍歷一棵樹，每次遍歷一個節點，判斷輸入節點是否在他子樹中

• 如果在子樹中，則分別遍歷他所有子節點，并判斷兩個輸入節點是否他們子樹中，

• 這樣從上到下遍歷，直到找到這樣一個節點，他自己的子樹中同時包含兩個輸入的節點，但是他的任何一個子節點都不會同時擁有這兩個節點，那么這就是公共祖先
  

• 我們舉例說明，如上圖：

  • 第一種情況，當輸入的是如上圖中65， 26 時候，還是中序遍歷，
  • 根節點中判斷是否存在有兩個節點，存在與否的判斷依然是用遞歸，如果存在，標記U,V中count=1即可
  • 遍歷21 ，依然存在，在遍歷24，依然存在，接著65 不存在，26 不存在，說明 24 是我們需要求解的值
  • 第二中情況，當輸入的是一個單鏈上的 32,77 時候，判斷就稍微不同
  • 依然中序遍歷當遍歷到21 時候，我們判斷都在右子樹中，接著遍歷31
  • 此時有不同情況，如果依然繼續遍歷判斷，我們會直接干到 32，發現都存在，到77，發現不存在，那么返回的是32
  • 顯然不是我們需要的，此處我們需要判斷31 的子節點是否是輸入節點，如果是，那么當前節點就是需要求解的

• 綜上也就三種情況，記錄 validateLeft為都存在left中， validateRight為都存在right中

  • 當遍歷到節點 N， 發現validateLeft = false && validateRight = false，說明一個在左，一個在右，那么得到解 N
  • 當遍歷到N 發現validateLeft = true，此時判斷 N 的left節點是否是輸入節點，如果是，那么N就是我們求解的，否則我們就遍歷N的left節點
  • 剩下的就是N 的validateRight = true情況，還是一樣，判斷right節點是否是輸入節點，那么N就是我們求解，否則我們遍歷N的right節點

• 經如上分析有如下代碼：

/*** 輸入兩個樹的節點node1， node2，找到他們最低公共祖先.* 最近公共祖先的定義為：對于有根樹 T 的兩個結點 p、q，最近公共祖先表示為一個結點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節點也可以是它自己的祖先）。** @author liaojiamin* @Date:Created in 16:31 2021/7/9*/ public class FindCommonNode {public static void main(String[] args) {BinaryNode node = new BinaryNode(null, null, null);BinarySearchTree searchTree = new BinarySearchTree();Random random = new Random();for (int i = 0; i < 10; i++) {node = searchTree.insert(random.nextInt(100), node);}BinaryNode node1 = new BinaryNode(29, null, null);node = searchTree.insert(node1, node);BinaryNode node2 = new BinaryNode(45, null, null);node = searchTree.insert(node2, node);BinaryNode result2 = findBinaryTree(node, node1, node2);System.out.println(result2.getElement());}/*** 非二叉排序樹*/public static BinaryNode findBinaryTree(BinaryNode tree, BinaryNode node1, BinaryNode node2) {if (tree == null || node1 == null || node2 == null) {return null;}//遞歸判斷修改狀態，所以每次都先初始化數量為0node1.setCount(0);node2.setCount(0);boolean left = validateNode(tree.getLeft(), node1, node2);node1.setCount(0);node2.setCount(0);boolean right = left ? false : validateNode(tree.getRight(), node1, node2);//情況一if (!left && !right) {return tree;}//情況二if (left) {//特殊情況二叉樹為單條鏈的情況if (tree.getLeft() == node1 || tree.getLeft() == node2) {return tree;}return findBinaryTree(tree.getLeft(), node1, node2);}//情況三if (right) {if (tree.getRight() == node1 || tree.getRight() == node2) {return tree;}return findBinaryTree(tree.getRight(), node1, node2);}return null;}/*** 判斷節點是否在二叉樹中*/public static boolean validateNode(BinaryNode tree, BinaryNode node1, BinaryNode node2) {if (tree == null) {return false;}if (tree.compareTo(node1) == 0) {node1.setCount(2);}if (tree.compareTo(node2) == 0) {node2.setCount(2);}if (node1.getCount() == 2 && node2.getCount() == 2) {return true;}boolean leftIn = validateNode(tree.getLeft(), node1, node2);boolean rightIn = validateNode(tree.getRight(), node1, node2);return leftIn || rightIn;} }

地獄模式

• 在以上方案中，當輸入是65， 26 時候，在判斷完都在13節點下時候，我們其實已經遍歷過21， 24 節點了，但是在之后的遍歷中，我們任然需要在遍歷21， 24，這種思路會出現很多重復的遍歷，更快速的解決方案還是有的

• 之前文章數據結構與算法–兩個鏈表中第一個公共節點給我們啟發，如下圖
  

• 上圖其實就是一顆二叉樹，只不過是斜的，之前用雙指針，求第一個公共節點，或者用棧空間求第一個相同的節點接口

• 受以上啟發，如果我們將兩個輸入節點U， V 的范問路徑分別放到兩個鏈表中，不就將二叉樹的問題轉為以上鏈表的問題。

• 還是如上圖
  分析如下：

  • 還是先根遍歷，當遍歷到13 節點，我在13節點對象中定義一個鏈表，用來存放已經走過的路徑，也就是 父節點路徑+ 本子節點，得到本節點路徑，
  • 那么遍歷13，將13 添加進去
  • 遍歷21，將21 添加到路徑 得到 13 ->21
  • 遍歷24，將24 添加到路徑 得到 13 ->21 ->24
  • 遍歷65，將65 添加到路徑 得到 13 ->21 ->24 ->65
  • 遍歷26 ，將26 添加到路徑 得到 13 ->21 ->24 ->26
  • 此時兩個節點都已經完成路徑的查詢，直接返回，接著分析兩個鏈表
  • 此處我們需要求的是最后一個公共節點，那么我們用棧，分別將兩個鏈表導入兩個棧，接著依次導出，求第一個非輸入節點，并且相同的節點 得到我們的解，

• 如上分析有如下代碼

/*** 輸入兩個樹的節點node1， node2，找到他們最低公共祖先.* 最近公共祖先的定義為：對于有根樹 T 的兩個結點 p、q，最近公共祖先表示為一個結點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節點也可以是它自己的祖先）。** @author liaojiamin* @Date:Created in 16:31 2021/7/9*/ public class FindCommonNode {public static void main(String[] args) {BinaryNode node = new BinaryNode(null, null, null);BinarySearchTree searchTree = new BinarySearchTree();Random random = new Random();for (int i = 0; i < 10; i++) {node = searchTree.insert(random.nextInt(100), node);}BinaryNode node1 = new BinaryNode(29, null, null);node = searchTree.insert(node1, node);BinaryNode node2 = new BinaryNode(45, null, null);node = searchTree.insert(node2, node);BinaryNode result = findBinarySearchTree(node, node1, node2);System.out.println(result.getElement());BinaryNode result2 = findBinaryTree(node, node1, node2);System.out.println(result2.getElement());BinaryNode result3 = buildBinaryLink(node, node1, node2);System.out.println(result3.getElement());}/*** 構造兩個單向鏈表*/public static BinaryNode buildBinaryLink(BinaryNode tree, BinaryNode node1, BinaryNode node2) {if (tree == null || node1 == null || node2 == null) {return null;}buildListNode(tree, node1, node2);ListNode node1List = node1.getLinkedList();ListNode node2List = node2.getLinkedList();MyStack<BinaryNode> stack1 = new MyStack<>();MyStack<BinaryNode> stack2 = new MyStack<>();while (node1List != null) {if (node1List.getBinaryNode() != null) {stack1.push(node1List.getBinaryNode());}node1List = node1List.getNext();}while (node2List != null) {if (node2List.getBinaryNode() != null) {stack2.push(node2List.getBinaryNode());}node2List = node2List.getNext();}//去掉node1， node2 節點，可能出現單鏈情況的樹，也就是node1， node2，同時出現在一個鏈中BinaryNode stackNode1 = stack1.pop();while (!stack1.isEmpty() && (stackNode1.compareTo(node1) == 0 || stackNode1.compareTo(node2) == 0)) {stackNode1 = stack1.pop();}BinaryNode stackNode2 = stack2.pop();while (!stack2.isEmpty() && (stackNode2.compareTo(node1) == 0 || stackNode2.compareTo(node2) == 0)){stackNode2 = stack2.pop();}do {if(stackNode1.compareTo(stackNode2) == 0){return stackNode1;}if(stack1.size() > stack2.size() && !stack1.isEmpty()){stackNode1 = stack1.pop();}else if(stack1.size() < stack2.size() && !stack2.isEmpty()){stackNode2 = stack2.pop();}else if(!stack2.isEmpty() && !stack1.isEmpty()){stackNode1 = stack1.pop();stackNode2 = stack2.pop();}else {return null;}}while (true);}/*** 構造節點路徑* */public static void buildListNode(BinaryNode tree, BinaryNode node1, BinaryNode node2) {if (tree == null) {return;}//初始化根節點路徑if (tree.getLinkedList() == null) {ListNode treeList = new ListNode(tree);tree.setLinkedList(treeList);}if (tree.getLeft() != null) {//將父節點路徑復制到子節點ListNode leftList = new ListNode();ListNode header = tree.getLinkedList();while (header != null) {ListNode newNode = new ListNode(header.getBinaryNode());MyLinkedList.addToTail(leftList, newNode);header = header.getNext();}//添加子節點本身，得到節點最終路徑MyLinkedList.addToTail(leftList, new ListNode(tree.getLeft()));tree.getLeft().setLinkedList(leftList);}if (tree.getRight() != null) {//將父節點路徑復制到子節點ListNode rightList = new ListNode();ListNode header = tree.getLinkedList();while (header != null) {ListNode newNode = new ListNode(header.getBinaryNode());MyLinkedList.addToTail(rightList, newNode);header = header.getNext();}//添加子節點本身，得到節點最終路徑MyLinkedList.addToTail(rightList, new ListNode(tree.getRight()));tree.getRight().setLinkedList(rightList);}//當輸入節點路徑都不為空，則表示已經查找完畢if (node1.getLinkedList() != null && node2.getLinkedList() != null) {return;}buildListNode(tree.getLeft(), node1, node2);buildListNode(tree.getRight(), node1, node2);} }

• 時間復雜度分析，因為從開始到輸入的兩個節點的路徑，只需要依次遍歷，每次遍歷復雜度是O(n)，但是每個節點的路徑負責還需要額外的開銷，每個節點路徑其實就是二叉樹的深度 O(logn) 那么最終的世界復雜度是O(n)

• 空間復雜度此處我們用額額外的鏈表存儲路徑，并且在分析鏈表時候用來額外的棧空間，鏈表只需要存儲路徑上的節點，也就是深度，那么空間復雜度O(logn)，棧同樣，O(logn)

• 今天的代碼分享就到這，之后還會有更多的練習，最后給一張神圖

上一篇：數據結構與算法–這個需求很簡單怎么實現我不管（發散思維）
下一篇：數據結構與算法–再來聊聊數組

總結

以上是生活随笔為你收集整理的数据结构与算法--死磕二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。

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