本篇文章講述Java數(shù)據(jù)結(jié)構(gòu)中關(guān)于二叉樹相關(guān)知識及常見的二叉樹OJ題做法講解（包含非遞歸遍歷二叉樹）

1.1二叉樹概念

一棵二叉樹是結(jié)點的一個有限集合，該集合：
1. 或者為空
2. 或者是由一個根節(jié)點加上兩棵別稱為左子樹和右子樹的二叉樹組成。

3. 二叉樹不存在度大于2的結(jié)點
4. 二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹

?1.2特殊的二叉樹

1. 滿二叉樹: 一棵二叉樹，如果每層的結(jié)點數(shù)都達到最大值，則這棵二叉樹就是滿二叉樹。也就是說，如果一棵二叉樹的層數(shù)為K，且結(jié)點總數(shù)是 ，則它就是滿二叉樹。

2. 完全二叉樹: 完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹是由滿二叉樹而引出來的。對于深度為K的，有n個結(jié)點的二叉樹，當且僅當其每一個結(jié)點都與深度為K的滿二叉樹中編號從0至n-1的結(jié)點一一對應時稱之為完全二叉樹。 要注意的是滿二叉樹是一種特殊的完全二叉樹。

?1.3二叉樹性質(zhì)

1. 若規(guī)定根結(jié)點的層數(shù)為1，則一棵非空二叉樹的第i層上最多有2^i-1 (i>0)個結(jié)點。
2. 若規(guī)定只有根結(jié)點的二叉樹的深度為1，則深度為K的二叉樹的最大結(jié)點數(shù)是 2^k-1(k>=0)。
3. 對任何一棵二叉樹, 如果其葉結(jié)點個數(shù)為 n0, 度為2的非葉結(jié)點個數(shù)為 n2,則有n0＝n2＋1。
4. 具有n個結(jié)點的完全二叉樹的深度k為log2(n+1)上取整。
5. 對于具有n個結(jié)點的完全二叉樹，如果按照從上至下從左至右的順序?qū)λ泄?jié)點從0開始編號，則對于序號為i的結(jié)點有：

• 若i>0，雙親序號：(i-1)/2；i=0，i為根結(jié)點編號，無雙親結(jié)點
• 若2i+1<n，左孩子序號：2i+1，否則無左孩子
• 若2i+2<n，右孩子序號：2i+2，否則無右孩子

6.當完全二叉樹有偶數(shù)個節(jié)點時，n1 = 1；

7.當完全二叉樹有奇數(shù)個節(jié)點時，n1 = 0；

8.n層k叉樹共有節(jié)點（k^n-1）/ (k-1);

1.4二叉樹基本性質(zhì)定理題

1. 某二叉樹共有 399 個結(jié)點，其中有 199 個度為 2 的結(jié)點，則該二叉樹中的葉子結(jié)點數(shù)為（ B）
A 不存在這樣的二叉樹
B 200
C 198
D 199

2.在具有 2n 個結(jié)點的完全二叉樹中，葉子結(jié)點個數(shù)為（A ）
A n
B n+1
C n-1
D n/2

3.一個具有767個節(jié)點的完全二叉樹，其葉子節(jié)點個數(shù)為（B）
A 383
B 384
C 385
D 386

4.一棵完全二叉樹的節(jié)點數(shù)為531個，那么這棵樹的高度為（B ）
A 11
B 10
C 8
D 12

1.5二叉樹遍歷基本操作

二叉樹的存儲結(jié)構(gòu)分為：順序存儲和類似于鏈表的鏈式存儲。

• 代碼實現(xiàn)：
• NLR：前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根結(jié)點--->根的左子樹--->根的右子樹。
• LNR：中序遍歷(Inorder Traversal)——根的左子樹--->根節(jié)點--->根的右子樹。
• LRN：后序遍歷(Postorder Traversal)——根的左子樹--->根的右子樹--->根節(jié)點。

public class TestBinaryTree {static class TreeNode {public char val;public TreeNode left;//左孩子的引用public TreeNode right;//右孩子的引用public TreeNode(char val) {this.val = val;}}/*** 創(chuàng)建一棵二叉樹 返回這棵樹的根節(jié)點** @return*/public TreeNode createTree() {TreeNode A = new TreeNode('A');TreeNode B = new TreeNode('B');TreeNode C = new TreeNode('C');TreeNode D = new TreeNode('D');TreeNode E = new TreeNode('E');TreeNode F = new TreeNode('F');TreeNode G = new TreeNode('G');TreeNode H = new TreeNode('H');A.left = B;A.right = C;B.left = D;B.right = E;C.left = F;C.right = G;E.right = H;//this.root = A;return A;}// 前序遍歷public void preOrder(TreeNode root) {if (root == null) {return;}System.out.println(root.val + " ");preOrder(root.left);preOrder(root.right);}// 中序遍歷void inOrder(TreeNode root) {if (root == null) {return;}inOrder(root.left);System.out.println(root.val + " ");inOrder(root.right);}// 后序遍歷void postOrder(TreeNode root) {if (root == null) {return;}inOrder(root.left);inOrder(root.right);System.out.println(root.val + " ");}

1.6二叉樹遍歷的前中后非遞歸寫法

//前序遍歷非遞歸public List<Integer> PreOrder(TreeNode root){List<Integer> list = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while (cur != null || !stack.isEmpty()){while (cur != null){list.add(cur.val);stack.push(cur);cur = cur.left;}cur = stack.pop();cur = cur.right;}return list;}//中序遍歷非遞歸public List<Integer> InorderTravelSal(TreeNode root){if (root == null){return new ArrayList<>();}List<Integer> list = new ArrayList<>();LinkedList<TreeNode> stack = new LinkedList<>();TreeNode cur = root;while (cur != null || !stack.isEmpty()) {while (cur != null) {stack.push(cur);cur = cur.left;}cur = stack.pop();list.add(cur.val);cur = cur.right;}return list;}//后序遍歷非遞歸public List<Integer> PostOrder(TreeNode root){if (root == null){return new ArrayList<>();}List<Integer> list = new ArrayList<>();Deque<TreeNode> stack = new LinkedList<>();TreeNode cur = root;TreeNode prev = null;while (cur != null || !stack.isEmpty()){while (cur != null){stack.push(cur);cur = cur.left;}TreeNode node = stack.peek();if (node.right == null || node.right == prev){list.add(node.val);stack.pop();prev = node;}else {cur = cur.right;}}return list;}

1.7二叉樹有關(guān)的基本操作

/*** 獲取樹中節(jié)點的個數(shù)：遍歷思路*/void size(TreeNode root) {if (root == null) {return;}nodeSize++;size(root.left);size(root.right);}/*獲取葉子節(jié)點的個數(shù)：子問題*/int getLeafNodeCount2(TreeNode root) {if (root == null) {return 0;}if (root.left == null && root.right == null) {return 1;}int leftSize = getLeafNodeCount2(root.left);int rightSize = getLeafNodeCount2(root.right);return leftSize + rightSize;}/*獲取第K層節(jié)點的個數(shù)*/int getKLevelNodeCount(TreeNode root, int k) {if (root == null) {return 0;}if (k == 1) {return 1;}int leftSize = getKLevelNodeCount(root.left, k - 1);int rightSize = getKLevelNodeCount(root.right, k - 1);return leftSize + rightSize;}/*獲取二叉樹的高度時間復雜度：O(N)*/public int maxDepth(TreeNode root) {if (root == null) {return 0;}int leftHeight = maxDepth(root.left);int rightHeight = maxDepth(root.right);return (leftHeight > rightHeight) ?(leftHeight + 1) : (rightHeight + 1);}// 檢測值為value的元素是否存在TreeNode find(TreeNode root, char val) {if (root == null) {return null;}if (root.val == val) {return root;}TreeNode leftTree = find(root.left, val);if (leftTree != null) {return leftTree;}TreeNode rightTree = find(root.right, val);if (rightTree != null) {return rightTree;}return null;//沒有找到}

二、二叉樹常見的OJ題

2.1相同的樹

100. 相同的樹 - 力扣（LeetCode）

class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {if(p == null && q == null){return true;}if(p != null && q == null || p == null && q != null){return false;}if(p.val != q.val){return false;}return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);}
}

?2.2對稱二叉樹

?101. 對稱二叉樹 - 力扣（LeetCode）

class Solution {public boolean isSymmetric(TreeNode root) {if (root == null){return true;}return isSymmetricChild(root.left,root.right);}public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree){if (leftTree != null && rightTree == null ||leftTree == null && rightTree != null){return false;}if (leftTree == null && rightTree == null){return true;}if (leftTree.val != rightTree.val){return false;}return isSymmetricChild(leftTree.left,rightTree.right) &&isSymmetricChild(leftTree.right,rightTree.left);}
}

與上一道相同的樹原理一致。

2.3反轉(zhuǎn)二叉樹

226. 翻轉(zhuǎn)二叉樹 - 力扣（LeetCode）

?

class Solution {public TreeNode invertTree(TreeNode root) {if (root == null){return null;}TreeNode tmp = root.left;root.left = root.right;root.right = tmp;invertTree(root.left);invertTree(root.right);return root;}
}

注意將子節(jié)點的每個節(jié)點都要反轉(zhuǎn)

2.4二叉樹的公共祖先

最近公共祖先的定義為：“對于有根樹 T 的兩個節(jié)點 p、q，最近公共祖先表示為一個節(jié)點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節(jié)點也可以是它自己的祖先）

236. 二叉樹的最近公共祖先 - 力扣（LeetCode）

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null){return null;}if(root == q || root == p){return root;}TreeNode leftRet = lowestCommonAncestor(root.left,p,q);TreeNode rightRet = lowestCommonAncestor(root.right,p,q);if(leftRet != null && rightRet != null){return root;}else if(leftRet != null){return leftRet;}else if(rightRet != null){return rightRet;}return null;}
}

注意在左右子樹中尋找節(jié)點，如果找到并返回節(jié)點，否則返回空

2.5二叉樹的層序遍歷

102. 二叉樹的層序遍歷 - 力扣（LeetCode）

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> list = new ArrayList<>();if (root == null) {return list;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int size = queue.size();List<Integer> tmp = new ArrayList<>();while (size > 0) {TreeNode cur = queue.poll();tmp.add((int) cur.val);if (cur.left != null) {queue.offer(cur.left);}if (cur.right != null) {queue.offer(cur.right);}size--;}list.add(tmp);}return list;}}

本題需要注意層序遍歷要使用隊列，先進先出。

2.6根據(jù)二叉樹前序與中序序列構(gòu)造二叉樹

給定兩個整數(shù)數(shù)組?preorder 和 inorder?，其中?preorder 是二叉樹的先序遍歷， inorder?是同一棵樹的中序遍歷，請構(gòu)造二叉樹并返回其根節(jié)點

105. 從前序與中序遍歷序列構(gòu)造二叉樹 - 力扣（LeetCode）

class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {return buildTreechild(preorder,inorder,0,inorder.length-1);}int i = 0;public TreeNode buildTreechild(int[] preorder,int[] inorder,int inbegin,int inend){if(inbegin > inend){return null;}TreeNode root = new TreeNode(preorder[i]);int rootIndex = findIndex(inorder,inbegin,inend,preorder[i]);i++;root.left = buildTreechild(preorder,inorder,inbegin,rootIndex-1); root.right = buildTreechild(preorder,inorder,rootIndex+1,inend);return root; }public int findIndex(int[] inorder,int inbegin,int inend,int key){for(int i = inbegin;i <= inend;i++){if(inorder[i]==key){return i;}}return -1;}
}

本題需要注意的點是只有給出前序或后續(xù)序列才能確定中序中根的位置