一,定義
一棵二叉樹中含有n(n>=0)個(gè)節(jié)點(diǎn),當(dāng)n=0時(shí),他是一棵空二叉樹;
當(dāng)n>0時(shí),他由一個(gè)根節(jié)點(diǎn)和兩棵互不相交的稱為左子樹和右子樹的二叉樹組成.
** 二叉樹的定義也是遞歸的 **
二,二叉樹常見的題目
一般來說,二叉樹的題目大部分都可以通過遍歷和他的遞歸定義以及搜索來解決
1,遍歷
先序,中序,后序,層次遍歷
先序遍歷LeetCode 144. Binary Tree Preorder Traversal
中序遍歷LeetCode 94. Binary Tree Inorder Traversal
后序遍歷LeetCode 145. Binary Tree Postorder Traversal
層次遍歷LeetCode 102. Binary Tree Level Order Traversal2,與遍歷相關(guān)的(也就是利用遍歷可以解決的題目)
判斷二叉排序樹是否合法---利用中序遍歷LeetCode 98. Validate Binary Search Tree
二叉樹"之"字形遍歷---層次遍歷LeetCode 103. Binary Tree Zigzag Level Order Traversal
二叉樹最大高度---層次,后序遍歷LeetCode 104. Maximum Depth of Binary Tree
二叉樹層次遍歷二---層次遍歷LeetCode 107. Binary Tree Level Order Traversal II
路徑和---層次,后序遍歷LeetCode 112. Path Sum
路徑和---層次,后序遍歷LeetCode 113. Path Sum II
葉子節(jié)點(diǎn)和---層次,后序遍歷LeetCode129. Sum Root to Leaf Numbers
從右看二叉樹---層次LeetCode 199. Binary Tree Right Side View3,利用定義或者搜索
判斷兩棵二叉樹是否相同LeetCode 100. Same Tree
二叉樹鏡像LeetCode 101. Symmetric Tree
二叉樹最大高度LeetCode 104. Maximum Depth of Binary Tree
路徑和LeetCode 112. Path Sum
路徑和LeetCode 113. Path Sum II
翻轉(zhuǎn)二叉樹LeetCode 226. Invert Binary Tree4,二叉樹的序列化和反序列化
LeetCode 297. Serialize and Deserialize Binary Tree5,二叉樹的構(gòu)建
先序和中序遍歷 或者 后序和中序遍歷可以唯一確定一棵二叉樹
LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal
LeetCode 106. Construct Binary Tree from Inorder and Postorder Traversal
