LeetCode-二叉树算法总结-层次遍历，路径总和等
希望通過寫下來自己學(xué)習(xí)歷程的方式幫助自己加深對(duì)知識(shí)的理解，也幫助其他人更好地學(xué)習(xí)，少走彎路。也歡迎大家來給我的Github的Leetcode算法項(xiàng)目點(diǎn)star呀~~
- 二叉樹常考算法整理
- 前言
- 二叉樹的類型
- 算法分類
- 遍歷(Traversal)問題
- 先序、中序與后序遍歷
- 利用兩種遍歷結(jié)果構(gòu)造二叉樹
- 遞歸問題
- 二叉樹最大深度
- 二叉樹最小深度
- 平衡二叉樹判斷
- 相同樹
- 對(duì)稱樹
- 路徑總和
- 二叉搜索樹/排序樹問題
- 驗(yàn)證二叉搜索樹
- 唯一二叉搜索樹
- 最低的二叉樹共同祖先
- 遍歷(Traversal)問題
前言
二叉樹即子節(jié)點(diǎn)數(shù)目不超過兩個(gè)的樹，基于這個(gè)基本特性，許多算法都圍繞這種樹本身或其變體而展開。
二叉樹的類型
此部分參考一句話弄懂常見二叉樹類型
根據(jù)樹的構(gòu)成特性，樹存在一些比較常見的類型，我們先來分別介紹一下：
- 滿二叉樹
除最后一層無任何子節(jié)點(diǎn)外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)二叉樹。
- 完全二叉樹
一棵二叉樹至多只有最下面的一層上的結(jié)點(diǎn)的度數(shù)（結(jié)點(diǎn)擁有的子樹數(shù)）可以小于2，并且最下層上的結(jié)點(diǎn)都集中在該層最左邊的若干位置上，則此二叉樹成為完全二叉樹。
- 平衡二叉樹
它是一棵空樹或它的左右兩個(gè)子樹的高度差的絕對(duì)值不超過1，并且左右兩個(gè)子樹都是一棵平衡二叉樹
- 二叉搜索/查找/排序樹
它或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：
- 若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；
- 若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；
- 它的左、右子樹也分別為二叉搜索樹
- 紅黑樹
屬于AVL樹（平衡二叉查找樹）的一種，對(duì)樹的高度的要求不如AVL樹那么嚴(yán)格（不是嚴(yán)格控制左、右子樹高度或節(jié)點(diǎn)數(shù)之差小于等于1），使得其插入結(jié)點(diǎn)的效率相對(duì)更高。
算法分類
遍歷(Traversal)問題
先序、中序與后序遍歷
對(duì)任一二叉樹結(jié)點(diǎn)，若以其本身為根結(jié)點(diǎn)（Root Node），它的左右子節(jié)點(diǎn)(left/right child)，那么遍歷指的就是以某種固定順序?qū)⒄麄€(gè)二叉樹的所有結(jié)點(diǎn)都過一遍。
按照根節(jié)點(diǎn)與子節(jié)點(diǎn)先后遍歷關(guān)系，一共有以下三種常見的遍歷順序：
- 先序遍歷(Preorder)
根結(jié)點(diǎn)-左子結(jié)點(diǎn)-右子結(jié)點(diǎn)
- 中序遍歷(Inorder)
左子結(jié)點(diǎn)-根結(jié)點(diǎn)-右子結(jié)點(diǎn)
- 后序遍歷(Postorder)
左子結(jié)點(diǎn)-右子結(jié)點(diǎn)-根結(jié)點(diǎn)
遍歷，根據(jù)實(shí)現(xiàn)思路，可以分為遞歸（Recursive）和非遞歸兩種方式。遞歸相對(duì)來說更為直觀易理解，但是由于遞歸需要不斷地多重地進(jìn)行函數(shù)自身調(diào)用，會(huì)需要消耗更多的棧空間。而非遞歸方式就是用一般的循環(huán)(Iteration)來進(jìn)行。（而其實(shí)由于二叉樹的結(jié)構(gòu)特性，許多相關(guān)的題目的解題思路都會(huì)存在遞歸和非遞歸兩種方式，只要多做幾道，就會(huì)自然體味到其中的規(guī)律。）
先給出遞歸實(shí)現(xiàn)的三種遍歷：
/** 遞歸的主要思想就是：* 由于是重復(fù)調(diào)用自身，故根據(jù)遍歷順序調(diào)整根節(jié)點(diǎn)與左右子節(jié)點(diǎn)的處理語句之間的相對(duì)順序即可。*///遞歸先序遍歷public static void recurivePreorder(TreeNode root){if(root==null)return;System.out.println(root.val);if(root.left!=null)recurivePreorder(root.left);if(root.right!=null)recurivePreorder(root.right);}//遞歸中序遍歷public static void recursiveInorder(TreeNode root){if(root==null)return;if(root.left!=null)recursiveInorder(root.left);System.out.println(root.val);if(root.right!=null)recursiveInorder(root.right);}//遞歸后序遍歷public static void recursivePostorder(TreeNode root){if(root==null)return;if(root.left!=null)recursivePostorder(root.left);if(root.right!=null)recursivePostorder(root.right);System.out.println(root.val);}- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
非遞歸實(shí)現(xiàn)三種遍歷：
/** 非遞歸的主要思想是：* 利用棧stack存下路過的結(jié)點(diǎn)，依照遍歷順序打印結(jié)點(diǎn)，利用stack回溯。*///非遞歸先序遍歷public static void nonRecurPreorder(TreeNode root){ArrayDeque<TreeNode> stack=new ArrayDeque<TreeNode>();while(root!=null || stack.size()!=0){if (root != null) { System.out.println(root.val); //訪問結(jié)點(diǎn)并入棧 stack.push(root); root = root.left; //訪問左子樹 } else { root = stack.pop(); //回溯至父親結(jié)點(diǎn) root = root.right; //訪問右子樹 } }}//非遞歸中序遍歷public static void nonRecurInorder(TreeNode root){ArrayDeque<TreeNode> stack=new ArrayDeque<TreeNode>();while(root!=null || stack.size()!=0){if(root!=null){stack.push(root);root=root.left; //訪問左子樹}else{root=stack.pop(); //回溯至父親結(jié)點(diǎn)System.out.println(root.val); //輸出父親結(jié)點(diǎn)root=root.right; //訪問右子樹}}}//非遞歸后序遍歷（相對(duì)來說，是二叉樹遍歷中最為復(fù)雜的一種）// 思路：如果當(dāng)前結(jié)點(diǎn)沒有左右子樹，或者左右子樹均已被訪問過，那么就直接訪問它；否則，將其右孩子和左孩子依次入棧。注釋：peek()函數(shù)返回棧頂?shù)脑?#xff0c;但不彈出該棧頂元素public static void nonRecurPostorder(TreeNode root){ArrayDeque<TreeNode> stack=new ArrayDeque<TreeNode>();TreeNode pre=null;TreeNode cur=null;stack.push(root);while(stack.size()!=0){cur=stack.peek();if((cur.left==null && cur.right==null) || (pre!=null && (pre==cur.left || pre==cur.right))){System.out.println(cur.val); //輸出父親結(jié)點(diǎn)pre=cur;stack.pop();}else{if(cur.right!=null)stack.push(cur.right);if(cur.left!=null)stack.push(cur.left);}}}- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
利用兩種遍歷結(jié)果構(gòu)造二叉樹
上面講到，二叉樹的遍歷方式一般分為先序、中序和后序三種，其中先序和中序，或者中序和后續(xù)的遍歷的結(jié)果就可以確定第三種的遍歷結(jié)果，也即確定了一棵具體的二叉樹。（此處默認(rèn)二叉樹無值相同的兩個(gè)結(jié)點(diǎn)）
- 利用先序與中序構(gòu)造二叉樹
（此處，我們僅對(duì)這道題進(jìn)行細(xì)致分析，另兩道題目是一模一樣的思路。）
先序代表了父親-左孩子-右孩子的順序，中序代表了左孩子-父親-右孩子的順序，因此，從遍歷序列的整體來看，先序序列的第一個(gè)結(jié)點(diǎn)代表的就是整棵樹的根結(jié)點(diǎn)，而我們?cè)谥行蛐蛄兄卸ㄎ坏竭@個(gè)結(jié)點(diǎn)后，中序序列這個(gè)結(jié)點(diǎn)以左的結(jié)點(diǎn)就是根結(jié)點(diǎn)左子樹上的所有結(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)以右的結(jié)點(diǎn)就是根結(jié)點(diǎn)右子樹上的所有結(jié)點(diǎn)。然后我們將先序序列按照由中序序列那里得知的劃分，找到左右子樹的劃分邊界。以此類推，我們就可以通過不斷地交替從兩個(gè)序列中獲得構(gòu)造二叉樹所需要的所有信息。
原題：LC105 Construct Binary Tree from Preorder and Inorder Traversal
public TreeNode buildTree(int[] preorder, int[] inorder) {if(preorder.length==0)return null;TreeNode root=new TreeNode(preorder[0]);if(preorder.length==1)return root;int leftSubTreeNodeNums=-1;for(int i=0;i<inorder.length;i++)if(inorder[i]==root.val) {leftSubTreeNodeNums=i;break;}root.left=buildTree(Arrays.copyOfRange(preorder, 1, leftSubTreeNodeNums+1), Arrays.copyOfRange(inorder,0,leftSubTreeNodeNums));root.right=buildTree(Arrays.copyOfRange(preorder, leftSubTreeNodeNums+1, preorder.length), Arrays.copyOfRange(inorder,leftSubTreeNodeNums+1,inorder.length));return root; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 利用中序與后序構(gòu)造二叉樹
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
遞歸問題
遞歸解二叉樹問題時(shí)，一般以一棵三結(jié)點(diǎn)或更多結(jié)點(diǎn)的小樹作為思考解法的參照物，然后考慮一下遞歸的返回情況（一般是碰到空結(jié)點(diǎn)的時(shí)候）如何處理。
二叉樹最大深度
原題：LC104 Maximum Depth of Binary Tree
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Note: A leaf is a node with no children.
Example:
Given binary tree [3,9,20,null,null,15,7],
3/ \ 9 20/ \ 15 7- 1
- 2
- 3
- 4
- 5
return its depth = 3.
- My Answer
- 1
- 2
- 3
- 4
- 5
- 6
- 7
二叉樹最小深度
原題：LC111 Minimum Depth of Binary Tree
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Note: A leaf is a node with no children.
Example:
Given binary tree [3,9,20,null,null,15,7],
3/ \ 9 20/ \ 15 7- 1
- 2
- 3
- 4
- 5
return its minimum depth = 2.
- My Answer
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
平衡二叉樹判斷
原題：LC110 Balanced Binary Tree
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as:
a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Example 1:
Given the following tree [3,9,20,null,null,15,7]:
3/ \ 9 20/ \ 15 7- 1
- 2
- 3
- 4
- 5
Return true.
Example 2:
Given the following tree [1,2,2,3,3,null,null,4,4]:
1/ \ 2 2/ \ 3 3/ \ 4 4- 1
- 2
- 3
- 4
- 5
- 6
- 7
Return false.
- My Answer
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
相同樹
原題：LC100 Same Tree
Given two binary trees, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical and the nodes have the same value.
Example 1:
Input: 1 1/ \ / \ 2 3 2 3[1,2,3], [1,2,3]Output: true- 1
- 2
- 3
- 4
- 5
- 6
- 7
Example 2:
Input: 1 1/ \2 2[1,2], [1,null,2]Output: false- 1
- 2
- 3
- 4
- 5
- 6
- 7
Example 3:
Input: 1 1/ \ / \ 2 1 1 2[1,2,1], [1,1,2]Output: false- 1
- 2
- 3
- 4
- 5
- 6
- 7
- My Answer
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
對(duì)稱樹
原題：LC101 Symmetric Tree
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree [1,2,2,3,4,4,3] is symmetric:
1/ \ 2 2/ \ / \ 3 4 4 3- 1
- 2
- 3
- 4
- 5
But the following [1,2,2,null,3,null,3] is not:
1/ \ 2 2\ \ 3 3- 1
- 2
- 3
- 4
- 5
Note:
Bonus points if you could solve it both recursively and iteratively.
- My Answer
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
路徑總和
原題：LC112 Path Sum
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
Note: A leaf is a node with no children.
Example:
Given the below binary tree and sum = 22,
5/ \ 4 8/ / \ 11 13 4/ \ \ 7 2 1- 1
- 2
- 3
- 4
- 5
- 6
- 7
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
- My Answer
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
二叉搜索樹/排序樹問題
二叉排序樹的特點(diǎn)前面提到過，即對(duì)于任一樹中結(jié)點(diǎn)，其左子樹的結(jié)點(diǎn)的值均小于它，而右子樹的結(jié)點(diǎn)的值均大于它。根據(jù)這個(gè)特性，也存在一系列相關(guān)的算法題。
而由于依然是二叉樹，故也常見用遞歸思路解決搜索樹相關(guān)的題目。
驗(yàn)證二叉搜索樹
LC98 Validate Binary Search Tree
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- Both the left and right subtrees must also be binary search trees.
Example 1:
Input:
2/ \1 3 Output: true- 1
- 2
- 3
- 4
Example 2:
5/ \ 1 4/ \ 3 6 Output: false- 1
- 2
- 3
- 4
- 5
- 6
Explanation: The input is: [5,1,4,null,null,3,6]. The root node’s value
is 5 but its right child’s value is 4.
- My Answer
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
唯一二叉搜索樹
LC96 Unique Binary Search Trees
Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?
Example:
Input: 3 Output: 5 Explanation: Given n = 3, there are a total of 5 unique BST's:1 3 3 2 1\ / / / \ \ 3 2 1 1 3 2/ / \ \ 2 1 2 3- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- My Answer
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
最低的二叉樹共同祖先
LC235 Lowest Common Ancestor of a Binary Search Tree
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”
Given binary search tree: root = [6,2,8,0,4,7,9,null,null,3,5]
_______6______/ \ ___2__ ___8__/ \ / \ 0 _4 7 9/ \ 3 5- 1
- 2
- 3
- 4
- 5
- 6
- 7
Example 1:
Input: root, p = 2, q = 8 Output: 6 Explanation: The LCA of nodes 2 and 8 is 6.- 1
- 2
- 3
Example 2:
Input: root, p = 2, q = 4 Output: 2 Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.- 1
- 2
- 3
- My Answer
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
總結(jié)
以上是生活随笔為你收集整理的LeetCode-二叉树算法总结-层次遍历，路径总和等的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 百度开源 FAQ 问答系统（AnyQ）安
- 下一篇： KeyError: ‘segment_i