目錄

1、將遍歷的結果放在list中

2、判斷兩棵樹是否相同

3、翻轉二叉樹

4、判斷平衡二叉樹

5、判斷二叉樹是否對稱

6、判斷是否為完全二叉樹

---

先創建一個二叉樹

public class BinaryTree {static class TreeNode {public char val;public TreeNode left;public TreeNode right;public TreeNode(char val) {this.val = val;}}public TreeNode creatTree() {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;return A;}

1、將遍歷的結果放在list中

將前序遍歷的結果存儲在list中

public class Solution {public List<Character>preorderTraversal(BinaryTree.TreeNode root){List<Character>list=new ArrayList<>(); //創建一個Listif (root==null){return list;}list.add(root.val); //將根放入List<Character>leftTree=preorderTraversal(root.left); //根的左子樹list.addAll(leftTree);List<Character>rightTree=preorderTraversal(root.right); //根的右子樹list.addAll(rightTree);return list;}}

---

2、判斷兩棵樹是否相同

要判斷兩棵樹是否相同，要同時判斷根是否相同，然后判斷兩棵樹的左子樹是否相同和右子樹是否相同。

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

---

3、翻轉二叉樹

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

---

4、判斷平衡二叉樹

class Solution{public boolean isBalance(BinaryTree.TreeNode root){if (root==null){return true;}int leftHeight=getHeight(root.left);int rightHeight=getHeight(root.right);return Math.abs(leftHeigh-rightHeigh<1&&isBalance(root.left)&&isBalance(root.right);}//求二叉樹的高度int getHeight(BinaryTree.TreeNode root){if (root==null){return 0;}int leftHeightDepth=getHeight(root.left);int rightHeightDepth=getHeight(root.right);return leftHeightDepth>rightHeightDepth?leftHeightDepth+1:rightHeightDepth+1;}}

---

5、判斷二叉樹是否對稱

class Solution{public boolean isSymmetric(BinaryTree.TreeNode root){if (root==null){return true;}return isSymmetricChild(root.left,root.right);}private boolean isSymmetricChild(BinaryTree.TreeNode leftTree, BinaryTree.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);}}

---

6、判斷是否為完全二叉樹

class Solution{boolean isCompleteTree(BinaryTree.TreeNode root){if (root==null){return true;}Queue<BinaryTree.TreeNode>queue=new LinkedList<>();queue.offer(root);while (!queue.isEmpty()){BinaryTree.TreeNode cur=queue.poll();if (cur!=null){queue.offer(cur.left);queue.offer(cur.right);}else {break;}}while (!queue.isEmpty()){BinaryTree.TreeNode tmp=queue.peek();if (tmp==null){queue.poll();}else {return false;}}return true;}}

---