The Code Pattern Under LeetCode: Tree (1)

Almost all problems of tree in leetcode can be converted into tree node traversal problem. 

In the review, there is summary for all kinds of traversal ways;

                                                                from leetcode: all reach 1-2-3-4-5 order

and for each of traversal way, we can also have the variation for the access from right -> left. 

So as the basic skill, we need knew to how travel the whole tree using both iteration and recursion for each of traversal way. 

Let's use the simple example from leetcode for detail explanation. 

 

Once we convert the problem to tree visiting way, it is pretty straightforward. when traveling the tree inorder, the numbers will be ordered in sequence.

when we write the code, firstly we write the code to trave tree inorder. and we add minor check  to check if the visited numbers is in sequence.. 

the code for InOrder visit:

	private void travelInOrderLeft2Right(TreeNode root, List<Integer> inOrderLeftAccessHistory) {
	if(root == null) return;
	travelInOrderLeft2Right(root.left, inOrderLeftAccessHistory);
	inOrderLeftAccessHistory.add(root.val);
	travelInOrderRight2Left(root.right, inOrderLeftAccessHistory);
	}

view raw SymmetricTree.java hosted with ❤ by GitHub

alternatively, the iteration version(remember it as your start point for most problem resolve):

	public void travelInOrderLeft2Right(TreeNode root) {
	Stack<TreeNode> stack = new Stack<>();
	TreeNode curr = root;
	Stack<Integer> acceHistory = new Stack<>();
	for(;!stack.isEmpty() || curr != null;) {
	for(;curr != null;) {
	stack.push(curr);
	curr = curr.left;
	}
	curr = stack.pop();
	acceHistory.push(curr.val);
	curr = curr.right;
	}
	}

view raw ValidateBinarySearchTree.java hosted with ❤ by GitHub

next step is to to add check when we add data to history access, see here. 

curr = stack.pop();
if(!acceHistory.isEmpty() && acceHistory.lastElement() >= curr.val) {
    isValid = false;
    break;
}

The full code will be as follow:

	public void travelInOrderLeft2Right(TreeNode root) {
	Stack<TreeNode> stack = new Stack<>();
	TreeNode curr = root;
	Stack<Integer> acceHistory = new Stack<>();
	boolean isValid = true;
	for(;!stack.isEmpty() || curr != null;) {
	for(;curr != null;) {
	stack.push(curr);
	curr = curr.left;
	}
	curr = stack.pop();
	if(!acceHistory.isEmpty() && acceHistory.lastElement() >= curr.val) {
	isValid = false;
	break;
	}
	acceHistory.push(curr.val);
	curr = curr.right;
	}
	}

view raw ValidateBinarySearchTree.java hosted with ❤ by GitHub